You are given an array A of length N which is initialised with 0. You will be given Q queries of two types:
1k: set value 1 at index k in array A
2y: print the smallest index x which is greater than or equal to y and having value 1. If there is no such index print 1.
Note: Indexing is 1 based
Input Format
First line contains two integers N and Q separated by a space.
The next Q lines contain the type of query (i.e. either a 1 or a 2), then a space, then for type 1 queries integer k and for type 2 queries integer y
Output Format
For each query type 2, print in new line, the smallest index x which is greater than or equal to y and having value 1. If there is no such index print 1.
Constraints
1≤n≤109
1≤q≤5∗105
1≤y,k≤n
For first query: 2 3, there is no index greater than or equal index 3, having value -1, so the answer is -1.
For second query: 1 2, set value -1 at index 2.
For third query: 2 1, index 2 is greater than index 1 , having value -1, so the answer is 2.
For fourth query: 2 3, there is no index greater than or equal index 3, having value -1, so the answer is -1.
For fifth query: 2 2, index 2 is equal to index 2 , having value -1, so the answer is 2.
