AKVOD05 - Ross generates Data

no tags 

Ross wants to complete the data set for his next research work. He has to generate a set of “N” non-negative integers. He already knows the first “K” values out of them. He knows how to generate the remaining values. Any of the remaining values will be the minimum non negative integer that does not exist in the previous “K” values.

For example, let the value of “N” is 7 and the value of “K” be 4 and the first “K” values be 0 4 3 2 then the next 3 values will be 1 0 4.

You just have to generate the “N”th value for his work.

Input

The first line will contain "T", the no. of test cases. Then "T" test cases follows. For each test case, the first line will contain two integers "N" and "K". The next line will contain "K" integers denoting the "K" values that he already knows.

Output

For each test case, output a single integer value that denotes the "N"th integer in his data set.

Constraints

1 <= T <= 10

1 <= K <= 10^5

K < N <= 10^8

0 <= Each of the first K values <= 10^8

Example

Input:
2
7 4
0 4 3 2
8 5
4 7 2 3 0

Output:
4
5

hide comments
nadstratosfer: 2019-06-29 07:01:40

My PyPy solution runs 4x faster than Vamsi's one but as opposed to his program, mine TLEs in raw Python. It appears testcases were added/strengthened in 2015 without rejudge. I'd like to be wrong, but if that's the case, that means trying to get the top 5 runtime is futile as well. Good problem otherwise.

praval_singhal: 2016-07-27 20:56:24

What is expected time complexity here? I did in k*log(k).

Last edit: 2016-07-28 20:11:17
praval_singhal: 2016-07-27 20:55:04

Finally After So many TLEs. AC. STL Rocks.

Jaswanth: 2015-08-20 15:15:55

Costed me 4 WA for thinking that the numbers are non repeating.

knb_dtu: 2014-03-18 14:16:58

@ankitism:Can you please explain second test case?

NISHANT RAJ: 2014-03-14 21:48:27

my algo will be in O(n^2) for worst case but got accepted in 0.03 sec...


Added by:Ankit Kumar Vats
Date:2014-02-22
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self