题目描述

奶牛们正在北上前往加拿大的桑德贝，体验文化风情并在苏必利尔湖阳光明媚的湖畔度假。作为称职的旅行策划者，贝西将著名的坎伯兰街上的Bullmoose酒店定为它们的下榻之处。这座巨大的酒店拥有$N$（$1 \leq N \leq 50,000$）间客房，全部位于一条极长的走廊同一侧（这样能更好地欣赏湖景）。

游客们以团体形式到达，每个团体$i$包含$D_i$（$1 \leq D_i \leq N$）位成员。他们来到前台，向当值的驼鹿Canmuu申请$D_i$间连续的客房。如果有可用且连续的客房，Canmuu会分配编号从$r$开始的$D_i$间房（即$r..r+D_i-1$），并尽可能选择最小的$r$值。如果没有足够的连续空房，Canmuu会礼貌地建议他们另寻住处。

同样，游客也会以连续房间的形式退房。每个退房请求包含参数$X_i$和$D_i$，表示释放从$X_i$号房开始的连续$D_i$间房（$1 \leq X_i \leq N-D_i+1$）。这些房间在退房前可能部分或全部为空。

你需要协助Canmuu处理$M$（$1 \leq M < 50,000$）个入住和退房请求。酒店初始状态为空置。

输入格式

• 第一行：两个整数$N$和$M$，用空格分隔
• 第$2$至$M+1$行：每行描述一个请求，格式为：
  • 入住请求：数字$1$后接$D_i$
  • 退房请求：数字$2$后接$X_i$和$D_i$

输出格式

• 对于每个入住请求，输出一行：
  • 若能分配，输出起始房号$r$
  • 若无法分配，输出$0$

样例输入

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

样例输出

1
4
7
0
5

题目来源

USACO 2008年2月黄金组