题目描述

每年夏天的热门活动就是在公园里举办的露天音乐会，舞台前方共摆放了n个座位，编号为1到n。你作为音乐会的管理人员，你站在音乐会的出入口控制人流，还需要为随时可能到场随时可能离开的观众们安排座位。共有m次观众的进出信息依次会提供给你，共有2种可能：进入，或者离开。

进入情况：会有一批d个观众一同前来，他们会要求你安排连续编号的d个座位。若无法安排，则这批观众会直接离开。若有多种安排方案，挑选编号最小的座位请d个人就座。并输出该编号。

离开情况：从x号座位开始，编号从小到大，共d个座位都会清空，无论这些座位原本是否有人。

输入输出格式

输入格式

输入文件concert.in 输入第一行为正整数n和m，n<=50000，m<=50000。接着共m行，每行第一个数为1或者2，1代表进入情况，2代表离开情况。若是1，则该行还有一个正整数d；若是2，则该行还有两个正整数x，d。保证：d<=n，x+d-1<=n。

输出格式

输出文件concert.out 输出共n行，每行一个正整数编号或者0代表无法安排。

输入输出样例

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

1
4
7
0
5

说明