一家旅馆共有N个房间，这N个房间是连成一排的，标号为1-N。

现在有很多旅客以组为单位前来入住，每组旅客的数量可以用$D\_i$来表示。

旅店的业务分为两种，入住和退房：

1、旅客入住时，第i组旅客需要根据他们的人数$D\_i$，给他们安排$D\_i$个连续的房间，并且房间号要尽可能的小。如果房间不够，则无法安排。

2、旅客退房时，第i组旅客的账单将包含两个参数$X\_i$和$D\_i$,你需要将房间号$X\_i$到$X\_i+D\_i-1$之间的房间全部清空。

现在你需要帮助该旅馆处理M单业务。

旅馆最初是空的。

输入数据

第一行输入两个用空格隔开的整数N和M。

接下来M行将描述M单业务：

“1 $D\_i$”表示这单业务为入住业务。

“2 $X\_i$ $D\_i$”表示这单业务为退房业务。

输出数据

每个入住业务输出一个整数，表示要安排的房间序列中的第一个房间的号码。

如果没办法安排，则输出0。

每个输出占一行。

数据范围

$1 \le D\_i \le N \le 50000$,
$1 \le M < 50000$

输入样例：

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

输出样例：

1
4
7
0
5

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解