Stock Market

There are a lot of people on the Tg. Mureș stock market. Some buy shares, others sell. Transactions are recorded electronically at Smart Software Company, where program¬mers are prepared to answer various questions. This morning, the business manager asked something from Rookie, a recently hired programmer, but he could not answer. If you succeed to answer the question, the manager will give you an award and – who knows – he might even hire you at the Smart Software Company.

Manager's question: What is the value of the transaction which is larger (or equal) than k – 1 other transactions?

Input Specification

The first line of the input contains the number of test cases t. The first line of each test case includes the number n (the total number of transactions in the Smart database) and the number k (with the meaning given in the requirement). Each of the following n lines contains an integer (positive numbers are incomes for the market, negative numbers represent payments). Two test cases are separated by an empty line.

Output Specification

For each test case, your program has to print on a separate line the value of the traded amount, that is, the kth smallest value in the Smart database.

Restrictions and Refinements

• 1 ≤ n ≤ 10⁶
• 1 ≤ k ≤ n
• –2³¹ – 1 ≤ traded amount ≤ 2³¹ – 1
• Numbers are not necessarily distinct.
• The smallest amount has the order number 1.

Sample Input

1. 1
2. 10 8
3. 2356700
4. -45001
5. 10023
6. 450
7. -19999023
8. 876
9. -76005
10. 876
11. 3299881
12. -451

download as text file

Output for Sample Input

1. 10023

download as text file

Explanation of Sample Input

The numbers in ascending order:

1. –19999023
2. –76005
3. –45001
4. –451
5. 450
6. 876
7. 876
8. 10023
9. 2356700
10. 3299881