题目描述

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

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

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

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

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

现在你需要帮助该旅馆处理$\red {M}$单业务。

旅馆最初是空的。

输入格式

第一行输入两个用空格隔开的整数$\red {N}$和$\red {M}$。

接下来$\red {M}$行将描述M单业务：

$\red {“1 D_i~”}$表示这单业务为入住业务。

$\red {“2 X_i~ D_i”}$表示这单业务为退房业务。

输出格式

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

如果没办法安排，则输出$\red {0}$。

每个输出占一行。

样例

输入样例

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

输出样例

1
4
7
0
5

提示

$\red {1≤D _i~ ≤N≤50000}$,

$\red {1≤M<50000}$