SUSTech Online Judge

Problem 1350 --[Bonus] K-th Largest Elements

1350: [Bonus] K-th Largest Elements

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 641 Solved: 88
[Submit][Status][Web Board]

Description

There is an array \(a[ 1... n ]\), which has \(n\) integers.

Consider all the consecutive intervals of \(a[ ]\) which have at least \(K\) integers. We find the \(K\)-th largest element from each of such intervals, and add these elements into an array \(B\) which is initially empty. Notice that the same element can be added for multiple times. Obviously, finally the length of \(B\) is \(\frac{(n+2-K)(n+1-K)}{2}\).

For example, \(a=[4,5,5,8,6]\) and \(K=4\). Then the consecutive intervals with at least \(K=4\) integers are \([4,5,5,8], [5,5,8,6], [4,5,5,8,6]\). After finding the \(K\)-th largest elements, we get \(B=[4,5,5]\).

Do you know what is the \(M\)-th largest integer in array \(B[ ]\)?

Input

The first line contains an integer \(T(1\leq T\leq 5)\), indicating the number of test cases.

For each test case, the first line contains three integers \(n(1\leq n\leq 10^5), K(1\leq K\leq n), M(1\leq M\leq \frac{(n+2-K)(n+1-K)}{2} )\). The second line contains \(n\) integers \(a[i] (1\leq a[i]\leq 10^9)\).

Output

For each test case, output the answer in one line.

Sample Input

1
5 4 1
4 5 5 8 6

Sample Output

HINT

Source

[Submit][Status]