11201120 SUSTech Online Judge
Problem 1120 --Skipping inquiry

1120: Skipping inquiry

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 224  Solved: 42
[Submit][Status][Web Board]

Description

Grace has n numbers. They are a1……an . Let M = sqrt(n), meaning the biggest integer which is less than or equal to the square root of n. And there are n queries. For each query, there are two integers x and y. You need to answer the M-th biggest number among ax, ax+y……(x + ky <= n) . If the number of the elements is less than M, please output -1.


Input

The first line will be an integer T, which is the number of test cases. (1 <= T <= 5). For each test case, the first line will be an integer n (1 <= n <= 40000). The second line will be n integers which are a1……an(1 <= ai <= 109). For the following n lines, each line contains two integers x and y 

Output

For each test output the M-th biggest element or -1 in one line.


Sample Input

1
5
1 2 3 4 5
1 1
2 2
3 3
4 4 
5 5

Sample Output

4
2
-1
-1
-1

HINT

Source

 

[Submit][Status]