You are given an array (initially which is empty) and also given two types of operations:
Given a number, insert the number into the array
Given a number, find the lowest integer not present in the array that is greater than or equal to the given number
The first line of the input contains the number of test cases $T \le 10$
First line of each test case contains two positive numbers $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 $q$ lines contain two integers $type$and $x$. ($1\leq type \leq 2$, $1 \leq x \leq n$). The first number $type$ is the query type and the second number $x$ is the operation argument. If the query type is $1$ 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 $2$ then we are asked to find the lowest integer not present in the array that is greater than or equal to the given number.
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.
Input | Output |
---|---|
1 10 5 1 1 2 2 2 1 1 4 2 4 | Case 1: 2 2 5 |
Input | Output |
---|---|
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 |