/*
Mail to : miyubai@gamil.com
Link : http://www.cnblogs.com/MiYu || http://m.shnenglu.com/MiYu
Author By : MiYu
Test : 1
Complier : g++ mingw32-3.4.2
Program : PKU_3667
Doc Name : HOTEL
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
inline int max ( int a, int b ) {
return a > b ? a : b;
}
struct segTree {
int left, right, lVal, rVal, mVal, cov;// cov -- > 0: 線段為空 1: 線段為滿 -1：2種情況都有
int mid () { return (left+right)>>1; }
int dis () { return right - left + 1; }
void set ( int flag ) { // 0: 線段為空 1: 線段為滿
if ( flag ){
cov = 1;
lVal = rVal = mVal = 0;
} else {
cov = 0;
lVal = rVal = mVal = right - left + 1;
}
}
}seg[160000];
void creat ( int left, int right, int rt = 1 ) { // 初始化線段
seg[rt].left = left;
seg[rt].right = right;
seg[rt].set (0);
if ( left == right ) return;
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
creat ( left, mid, LL );
creat ( mid + 1, right, RR );
}
void modify ( int left, int right, int flag, int rt = 1 ) {
if ( seg[rt].left >= left && seg[rt].right <= right ) { //如果線段被覆蓋, 直接按flag標(biāo)記處理,返回
seg[rt].set ( flag ); return;
}
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( seg[rt].cov != -1 ) { // 如果線段不是混合情況(即線段是被覆蓋的), 把標(biāo)志下傳
seg[LL].cov = seg[RR].cov = seg[rt].cov;
seg[LL].set ( seg[LL].cov );
seg[RR].set ( seg[RR].cov );
}
if ( right <= mid ) modify ( left, right, flag, LL ); //遞歸更新線段
else if ( left > mid ) modify ( left, right, flag, RR );
else {
modify ( left, mid, flag, LL );
modify ( mid + 1, right, flag, RR );
}
if ( seg[LL].cov == 0 && seg[RR].cov == 0 ) seg[rt].cov = 0; //線段為空
else if ( seg[LL].cov == 1 && seg[RR].cov == 1 ) seg[rt].cov = 1; //線段滿
else seg[rt].cov = -1; // 2種情況都有
seg[rt].mVal = max(seg[LL].rVal+seg[RR].lVal,max(seg[LL].mVal, seg[RR].mVal)); // 線段的更新, 經(jīng)典部分
seg[rt].lVal = seg[LL].lVal + ( seg[LL].cov == 0 ? seg[RR].lVal : 0 );
seg[rt].rVal = seg[RR].rVal + ( seg[RR].cov == 0 ? seg[LL].rVal : 0 );
}
int query ( int val, int rt = 1 ) {
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( seg[rt].cov == 0 && seg[rt].mVal >= val ) { //線段為空,且可用,直接返回線段左端點(diǎn)
return seg[rt].left;
} else if ( seg[rt].cov == -1 ) { //分三種 情況處理 左 左右 右 處理
if ( seg[LL].mVal >= val ) return query ( val, LL );
else if ( seg[LL].rVal + seg[RR].lVal >= val ) return mid - seg[LL].rVal + 1;
else if ( seg[RR].mVal >= val )return query ( val, RR );
}
return 0;
}
int main ()
{
int N, M, left, right, val, choice;
while ( scanf ( "%d%d", &N,&M ) == 2 ) {
creat ( 1, N );
while ( M -- ) {
scanf ( "%d", &choice );
switch ( choice ) {
case 1 : scanf ( "%d",&val );
printf ( "%d\n", left = query ( val ) );
if ( left != 0 ) {
right = left + val - 1;
modify ( left, right, 1 );
}
break;
case 2 : scanf ( "%d%d",&left, &val );
right = left + val - 1;
modify ( left, right, 0 );
break;
}
}
}
return 0;
}