小X所在的森林里有$N$株树排成一条直线，从左至右由$1$至$N$编号。每一株树可以分为"健康"与"腐烂"两种状态。一开始全部树都是"健康"的。
森林裏的树有一个神奇的特性：如果在第$t$秒时第$i$株树是腐烂的，那么第$i-1$株树会在时间$t+1$变成腐烂的。而且，腐烂了的树永远不会回复健康。
因为小X很贪玩，他会在第$1$至$Q$秒内每秒进行以下其中一种操作：
- 操作1: 把第$X$株树变成腐烂。如果它本来已经腐烂，则没有改变。
- 操作2: 找出第一株在树$X$右边而且腐烂的树（注意第$X$株樹不計算在其中）。
给出小X会进行的操作，你的任务是在每个操作2时协助小X找出要求的树。
输入格式
输入的第一行包含两个正整数$N$和$Q$。
之后$Q$行，每行包含两个整数$T$和$X$，代表第$i$秒操作的种类和该操作的$X$的值。
输出格式
对于每一个操作2，输出该操作找出的树的编号。如果没有找到的树，输出-1。
数据范围
对于所有测试数据，保证：
$1 \le N,Q \le 10^5$
$1\le X \le N$
$T=1$ 或 $2$
| 数据编号 | $N \le$ | $Q \le$ |
|---|---|---|
| 1-4 | $1000$ | $1000$ |
| 5-10 | $10^5$ | $10^5$ |
Sample Test Cases
| Input | Output | |
|---|---|---|
| 4 4 2 1 1 4 2 1 2 1 |
-1 3 2 |
|
一开始，全部树都是健康的。 第一秒时，小X想求出在$1$号树右边的第一株腐烂的树。因为没有树是腐烂的，因此输出$-1$。 第二秒时，小X把$4$号树变成腐烂。 因爲$4$号树已经腐烂，$3$号树在第三秒时也变爲腐烂。 第三秒时，腐烂的树为$3$和$4$。因此在$1$右边第一株腐烂的树是$3$号树。 因爲$3$号树已经腐烂，$2$号树在第四秒时也变爲腐烂。 第四秒时，腐烂的树为$2$，$3$和$4$。因此在$1$右边第一株腐烂的树是$2$号树。 |
||
| /forest2.in | /forest2.ans | |
此样例满足第5-10测试点的限制 |
||
Scoring: Per Case
Authored by s22l19, s23f32 and wy24215
Appeared in 2025 Mini Comp 4 [WY Interschool Pre-SDIC]