题目描述

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

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

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

• 入住：第 $i$ 组旅客需要根据他们的人数 $D_i$，给他们安排 $D_i$ 个连续的房间，并且房间号要尽可能的小。如果房间不够，则无法安排。
• 退房：第 $i$ 组旅客的账单将包含两个参数 $X_i$ 和 $D_i$，你需要将房间号 $X_i$ 到 $X_i + D_i - 1$ 之间的房间全部清空。

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

旅馆最初是空的。

输入格式

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

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

• 1 Di 表示这单业务为入住业务。
• 2 Xi Di 表示这单业务为退房业务。

输出格式

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

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

每个输出占一行。

样例

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

1
4
7
0
5

样例解释

初始状态：
房间总数 $N = 10$，全部为空。

业务 1：入住 $D = 3$
找到最小的连续 $3$ 个空房间，从房间 $1$ 开始。
输出：$1$
房间状态：$[1, 2, 3]$ 已占用，其余为空。

业务 2：入住 $D = 3$
最小的连续 $3$ 个空房间从房间 $4$ 开始。
输出：$4$
房间状态：$[1, 2, 3, 4, 5, 6]$ 已占用，其余为空。

业务 3：入住 $D = 3$
最小的连续 $3$ 个空房间从房间 $7$ 开始。
输出：$7$
房间状态：$[1, 2, 3, 4, 5, 6, 7, 8, 9]$ 已占用，$[10]$ 为空。

业务 4：入住 $D = 3$
此时只有 $1$ 个空房间，无法安排连续 $3$ 个空房间。
输出：$0$
房间状态不变。

业务 5：退房 $X = 5, D = 5$
清空房间 $[5, 6, 7, 8, 9]$。
房间状态：$[1, 2, 3, 4]$ 已占用，$[5, 6, 7, 8, 9, 10]$ 为空。

业务 6：入住 $D = 6$
最小的连续 $6$ 个空房间从房间 $5$ 开始。
输出：$5$
房间状态：$[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$ 全部占用。

数据范围

• $1 \leq D_i \leq N \leq 50000$
• $1 \leq M \leq 50000$