问题描述

Dr.Kong有一个容量为N MB (1 <= N <= 50,000)的存储磁盘,不妨设地址空间编号为1到N。现在他需要安装一些软件， 每个软件要占用一定大小的容量且必须装在连续的地址空间里。比如发出指令“ 1 100 ”，表示需要申请100 MB的存储空间。如果有多个满足条件的连续空间，则选择起始地址最小的一个进行分配。若没有足够的连续空间，将不安装此软件（即使有足够多的不连续存储空间）。

系统可以不定时的卸载软件，释放磁盘的空间。比如：发出“ 2 23 100 ”，表示释放起始地址为23的连续100MB大小的容量。释放时，不需要考虑这些空间里是否安装过软件。

请你编写一个程序，帮助Dr.Kong处理M (1 <= M <= 50,000)个按指令次序请求的任务。第一个请求到来前，磁盘是空的。

输入格式:

第1行: N M

第2..M+1行: 每行描述了一个请求，如果是申请，则用2个数字 1 Mi 表示；

如果是释放，则用3个数字 2 Di Mi表示。数据之间用一个空格隔开

（1<=Di ,Mi<= 50,000）

输出格式:

对于每个申请指令，输出1行。如果请求能被满足，输出满足条件的最小起始地址；如果请求无法被满足，输出0。

输入样例

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

输出样例

1
4
7
0
5