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
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 

Vipul Srivastava:
20170808 15:58:11
I am using set for my solution and the complexity is Qlogn I am getting TLE, can someone suggest if its a problem using stl for the solution? 

pvsmpraveen:
20170808 15:45:14
QlogN is sufficient. 

starbot:
20170807 09:35:39
@vipul seems so 

sas1905:
20170805 13:32:22
For Type 2 print the smallest index(if exists) greater than equal to y which has the value of 1. 

Vipul Srivastava:
20170805 11:00:31
Is qlog(n) insufficient for this problem? 
Added by:  Sandeep Kumar Singh 
Date:  20170804 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 