[Usaco2008 Feb]Hotel 旅馆

奶牛们计划前往苏必利尔湖畔旅游，享受当地的湖光山色。作为旅行的策划者和负责人，贝茜选择了一家湖边的著名旅馆。

旅馆共有 $N$ 间客房，它们位于同一层，并按编号顺次排列。贝茜一行和其他游客会分批来到旅馆，希望预订 $D_i$ 间连续的客房。

对于每个订房请求，如果存在一个编号 $r$ ，使得编号为 $r,r+1,\ldots,r+D_i-1$ 的客房均为空闲状态，则服务员会将这些客房分配给该批游客。如果有多个满足条件的 $r$ ，服务员会选择其中最小的一个；如果不存在满足条件的 $r$ ，则该请求无法满足。

旅馆也会批量处理退房请求。每个退房请求由 $X_i$ 和 $D_i$ 描述，表示编号为 $X_i,X_i+1,\ldots,X_i+D_i-1$ 的客房全部变为空闲状态。在退房前，这些客房中的一部分甚至全部都可能原本无人入住。

你需要编写程序，按照输入顺序处理 $M$ 个订房或退房请求。在第一个请求到来之前，旅馆中的所有客房均为空闲状态。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $M$ ，分别表示客房数量和请求数量。

接下来 $M$ 行，第 $i$ 行描述第 $i$ 个请求：

对于每个订房请求，输出一行一个整数：

退房请求不产生输出。

本题为 USACO 2008 February 试题「Hotel 旅馆」，题面与测试数据整理自 BZOJ。