描述

参考样例，第一行输入\(n，m\) ，\(n\)代表有\(n\)个房间，编号为\(1-n\)，开始都为空房，\(m\)表示以下有\(m\)行操作，以下每行先输入一个数 \(i\) ，表示一种操作：

若\(i\)为\(1\)，表示查询房间，再输入一个数\(x\)，表示在\(1-n\)房间中找到长度为\(x\)的连续空房，输出连续\(x\)个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为\(x\)的连续空房，输出\(0\)。若找得到，在这\(x\)个空房间中住上人。

若\(i\)为\(2\)，表示退房，再输入两个数 \(x，y\) 代表 房间号 \(x-x+y-1\) 退房，即让房间为空。

格式

输入格式

• Line 1: Two space-separated integers: \(N\) and \(M\)

• Lines \(2..M+1\): Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and \(D_i\) (b) Three space-separated integers representing a check-out: 2, \(X_i\), and \(D_i\)

输出格式

• Lines 1.....: For each check-in request, output a single line with a single integer \(r\), the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output \(0\).

样例1

输入样例1

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

输出样例1

1
4
7
0
5