Subsequence Fight

arnab_1810043 RUET CodeSmash 2020
Limits 1s, 256 MB

You are given an array a1,a2,,an{a_1, a_2, \dots, a_n} consisting of nn distinct integers and an integer kk. You can choose any subsequence of size kk from the array in which the subsequence's elements are in sorted order, lowest to highest. Your task is to calculate the maximum possible median among the subsequence you can choose. If there is no such subsequence, print 1-1.

A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.

median of a sequence of integers of length kk is the number standing on the k2{\lceil \frac{k}{2} \rceil}-th (rounding up) position in the increasing ordering of its elements. Positions are numbered starting from 11. For example, a median of the sequence [20,30,40,50,60,70][20,30,40,50,60,70] is the 62{\lceil \frac{6}{2} \rceil}-th element, so it is 4040. There exists other definitions of the median, but in this problem, we use the described definition.

Input

The first line contains one integer tt (1t105){(1 \le t \le 10^5)} - the number of test cases. Then tt cases follow.

The first line of each test case contains two space-separated integers: nn and kk (1kn105){(1 \le k \le n \le 10^5)}.

The second line of each test case contains nn space-separated integers a1,a2,,an{a_1, a_2, \dots, a_n} (1ai106){(1 \le a_i \le 10^6)} - the array aa. It is guaranteed that all elements are distinct.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5.

Output

For each test case, output the maximum possible median. If no such median exists, print 1-1.

Sample

InputOutput
3
4 2
1 2 4 3
4 3
1 5 3 4
2 2
2 1
2
3
-1


Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.