Little Elephant and Intervals
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.
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.
One line is to be printed which is the nth smallest element in the final list arranged in the non-decreasing order.
n<=total no. of elements in the final list, but never greater than 2000000000
1 4 7
5 6 8
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