SOLVEIT  SOLVEIT
Problem setter of INSOMNIA , MNNIT Allahabad decided to set a easy problem for all coders so that they can easily solve the problem and boost their confidence for rest of INSOMNIA.
The problem is a follows: You are given an array of size n while is initialized with 0.You will be given q queries of two types
Type 1: set in (input value)index k to 1
Type 2: print the index which has value 1 and is greater or equal to input index y
If there is no such value print 1
Note: Indexing is 1 based;
Input
First line contains two integers n and q separated by spaces
Next q lines contains type of query and for type 1 query integer k separated by a space and for type 2 integer y separated by a space;
1<=n<=10^6
1<=q<=10^6
1<=y,k<=n
Output
Print a single line for each query type 2 containing index which has value 1 and is greater or equal to input index y
Example
Input: 5 5
2 3
1 2
2 1
2 3
2 2 Output: 1
2
1
2
hide comments
vineetjai:
20200916 08:24:09
fastio+set+'\n' => gives AC 

Rafail Loizou:
20200913 10:05:16
I made 2 implementations with different data structures. In one case the data structure was in stack memory and in the other it was in the heap memory. Both cases passed when I used scanf/printf and both failed when I used cin/cout with fast I/O " ios::sync_with_stdio(false); " and "cin.tie(0);"


feodorv:
20200522 13:47:09
Alas, test cases are weak. O(nq/32) is possible. 

aditya_rev:
20200512 15:41:23
Dang. How can i get SIGXFSZ verdict? Could someone kindly to explain why this happened? 

kshubham02:
20190718 12:25:37
(Comment of anirudnits) +1 

anirudnits:
20180609 12:27:40
lower_bound(s.begin(),s.end(),y) > TLE


starbot:
20170928 21:58:15
for those using set..lowerbound has log^2 complexity...so it might not work 

mani_123:
20170809 12:35:28
answer is 2


Vipul Srivastava:
20170808 17:46:15
I am using scanf 

pvsmpraveen:
20170808 16:48:32
I used stl set too... if u use cin , cout , use fast i/o Last edit: 20170808 16:49:22 
Added by:  Sandeep Kumar Singh 
Date:  20170804 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 