MEX Revised

NAbdulla Ada Lovelace National Gir...
Limits 500ms, 512 MB

You are given an array (initially which is empty) and also given two types of operations:

  1. Given a number, insert the number into the array

  2. Given a number, find the lowest integer not present in the array that is greater than or equal to the given number

Input

The first line of the input contains the number of test cases T10T \le 10

First line of each test case contains two positive numbers n,q(1n1000000,1q100000)n, q (1 \le n \le 1000000, 1 \le q \le 100000)- the maximum possible number to be inserted in the array and the number of queries respectively.

Each of the next qq lines contain two integers typetypeand xx. (1type21\leq type \leq 2, 1xn1 \leq x \leq n). The first number typetype is the query type and the second number xx is the operation argument. If the query type is 11 then we are asked to insert the argument into the array (all the argument numbers for this type of operation will be pairwise distinct in a test case). If the query type is 22 then we are asked to find the lowest integer not present in the array that is greater than or equal to the given number.

Output

For each test case, print the case number in the format “Case case_no:” on a line(replace case_no with the correct case number). After that print an integer for each second type of query described in the input.

Samples

InputOutput
1
10 5
1 1
2 2
2 1
1 4
2 4
Case 1:
2
2
5
InputOutput
2
10 5
1 2
1 3
1 4
2 4
2 1
10 8
1 2
1 4
2 4
1 3
2 8
1 8
2 8
2 9
Case 1:
5
1
Case 2:
5
8
9
9

Submit

Login to submit.

Statistics

59% Solution Ratio
Farhan20Earliest, 2M ago
steinumFastest, 0.0s
JIANEELightest, 5.5 kB
JIANEEShortest, 568B
Toph uses cookies. By continuing you agree to our Cookie Policy.