All Submissions


Little elephant from the zoo of Lviv loves intervals. He is so obsessed with the intervals that he writes a list of integers in the form of several intervals of the form (left, right) where left<=right. Each of these intervals represent a set consisting of the integers starting from left to right (both inclusive). Union of all these sets constitutes the list that Little Elephant wants to be represented. Each element is repeated once for each interval they appear in.
So, if little elephant writes the intervals (1, 5), (4, 6) and (7, 8), then he actually infers the list [1, 2, 3, 4, 4, 5, 5, 6, 7, 8] which is the union of all the intervals but an integer gets repeated in the final list if they occur in multiple intervals, like 4 is repeated twice as it occurs in first two intervals, similarly for 5. The final list is to be considered in non-decreasing order.

Considering the final list in non decreasing order, little elephant wants to know the nth (starting from 0) smallest element. For example in the aforementioned case the 4th smallest element (0-based) is 4.

Input
First line gives T, the number of test cases. This number is followed by T test cases. Each test case consists of 4 lines. Fist line gives the number of intervals, N. The second line gives the array L of size N. L[i] is the lower limit(inclusive) of the ith interval. The third line gives the array R of size N. R[i] gives the upper limit(inclusive) of the ith interval. The fourth line of the test case gives the value of n.

Output
One line is to be printed which is the nth smallest element in the final list arranged in the non-decreasing order.

Contraints
-2000000000<=L[i]<=2000000000
-2000000000<=R[i]<=2000000000
L[i]<=R[i]
N<=100000
n<=total no. of elements in the final list, but never greater than 2000000000

Sample Input
2
3
1 4 7
5 6 8
4
2
1 5
3 7
4

Sample Output
4
6

Explanation of second test case: The final list is [1 2 3 5 6 7]. The fourth element (0-based) is 6.

Problem Setter:Dhruva Bhaswar

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0