题目描述

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

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

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

• 旅客入住时，第 $i$ 组旅客需要根据他们的人数$D_i$，给他们安排 $D_i$个连续的房间，并且房间号要尽可能的小。如果房间不够，则无法安排。
• 旅客退房时，第$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。

每个输出占一行。

样例

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

1
4
7
0
5

数据范围

$1≤D_i≤N≤50000, 1≤M≤50000$

来源

• POJ3667
• 算法竞赛进阶指南