LOTTERY - Tickets lottery

no tags 

Byteland organizes this year's Soccer World Cup. Because of the mismanagement of the organizing team almost all tickets are sold out. But one radio station still has some tickets which will be raffled. Specifically, the radio station has announced a telephone game, where participants can choose a number between 1 and 1.000.000.000, and after each day the person who has chosen the kth smallest number will win one ticket. A special rule is in place which disallows people to choose a number which was already chosen by someone else (in this case the person is asked to choose another number).

Martin, a fanatic soccer fan without tickets, bribed Robert H., an employee of the radio station, by promising small gifts for telling him a current winning number: "A fine basket with specialities from the black forest, including some really good sausages, ham and - hold on to your seat - a wonderful KuKuClock! And a beer mug, too! Do I leave you any choice???"

Now Robert is in trouble and asks you if you can write a program which will tell him the kth smallest number at any time of the game.

 

Input

The first line of the input consists of the number of test cases to follow. Each test case starts with a line containing the number of telephone calls c (1 ≤ c ≤ 500000) followed by the number k (1 ≤ k ≤ min(c,100000)). The following c lines specify the chosen numbers in chronological order of the phone calls. You can assume that all chosen numbers are unique, except the number 0 which indicates that Martin called and asked for the current kth smallest number.

Output

For each line in the input with a zero print a line with the current kth smallest number (or -1 if there are currently less than k chosen numbers).

Example

Input:
2
2 1
1337
0
7 2
4711
0
4
0
210706
3
0
Output:
1337
-1
4711
4

hide comments
pavlopare: 2023-01-29 04:55:29

too many words


Added by:Adrian Kuegel
Date:2006-05-15
Time limit:4.881s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL GOSU JS-RHINO
Resource:Ulm Algorithm Course SoSe 2006