题目描述

\(N\)张纸牌从左到右摆成一排，初始时每张纸牌都是正面朝上。
给出以下两种操作方式：
（1）给定参数\(D\)：选取连续\(D\)张正面朝上的纸牌翻转，若有多种选法则优先选择最左边的区间；
（2）给定参数\(X\)和\(D\)：将第\(X \sim X+D-1\)张纸牌变为正面朝上。
给定\(M\)次操作。对于每次操作（1），请你输出被翻转的区间是从第几张牌开始的。如果不存在连续的\(X\)张正面朝上的纸牌，输出0。

输入格式

第一行是两个正整数\(N, M\)；
之后\(M\)行，每行2~3个正整数，顺次表示每次操作。第一个数\(C\)表示操作方式，\(C=1\)时给出参数\(D\)，\(C=2\)时给出参数\(X,D\)。
30%的数据：\(N \le 2000, \quad M \le 1000\)；
100%的数据：\(N \le 2 \times 10^5, \quad M \le 5 \times 10^4, \quad X+D-1 \le N\)。
数据随机生成，且保证\(0.1\% \le D / N \le 20\%\)。

输出格式

对于每次操作（1），输出一行表示答案。

样例

input

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

output

1
4
7
0
5

限制

Time limit: 1 sec
Memory limit: 128 megabytes

来源

From PKU Online Judge (POJ 3667)