第k小的数

Time Limit: 5000 ms Memory Limit: 65536 KiB

Problem Description

现有一个包含n个整数(1<=n<=900000)的无序序列(保证序列内元素各不相同),输入一个整数k(1<=k<=n),请用较快的方式找出该序列的第k小数并输出。

Input

多组输入。

首先输入一个数据组数T(1<=T<=100)

接下来是T组数据。

每组数据有两行。

第一行先输入两个整数,n和k。

接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。

Output

对于每组数据,输出该组数据中第k小的数num。

Sample Input

1
6 4
3 2 5 1 4 6

Sample Output

4

Hint

Source

axuhongbo