The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

The cows and other visitors arrive in groups of size D_i (1 ≤ D_i ≤ N) and approach the front desk to check in. Each group i requests a set of D_i contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+D_i-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters X_i and D_i which specify the vacating of rooms X_i ..X_i +D_i-1 (1 ≤ X_i ≤ N-D_i+1). Some (or all) of those rooms might be empty before the checkout.

Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and D_i (b) Three space-separated integers representing a check-out: 2, X_i, and D_i

* Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

/*

    线段树区间合并：query操作实现查询一段连续区间的左端点

                    update操作实现更新某段区间

                    PushUP操作实现合并左右儿子的区间

                    PushDown操作实现延迟标记向儿子下移

*/

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define mid (L+R)/2

#define lson rt*2,L,mid

#define rson rt*2+1,mid+1,R

const int maxn=60000;

//分别记录结点左端、右端及结点表示的连续区间长度

int l_sum[maxn*4],r_sum[maxn*4],rt_sum[maxn*4];

int cover[maxn*4];//标记结点状态，空、满、初始值

void build(int rt,int L,int R){

    l_sum[rt]=r_sum[rt]=rt_sum[rt]=(R-L+1);

    cover[rt]=-1;

    if(L==R)

        return;

    build(lson);

    build(rson);

}

void PushUP(int rt,int len){

    l_sum[rt]=l_sum[rt*2];

    r_sum[rt]=r_sum[rt*2+1];

    if(l_sum[rt]==len-(len/2)){

    //如果左儿子左端连续区间长度为左儿子结点管辖长度，则说明该结点左端连续区间可以扩增，继续加上右儿子的从左端连续的区间

        l_sum[rt]+=l_sum[rt*2+1];

    }

    if(r_sum[rt]==len/2){

    //如果右儿子右端连续区间长度为右儿子结点管辖长度，则说明该结点右端连续区间长度可以扩增，继续加上左儿子从右端连续的区间

        r_sum[rt]+=r_sum[rt*2];

    }

    //用左右儿子区间长度的最大值或合并后的最大值来更新该结点的区间长度

    rt_sum[rt]=max(max(rt_sum[rt*2],rt_sum[rt*2+1]),r_sum[rt*2]+l_sum[rt*2+1]);

}

void Pushdown(int rt,int len){

    if(cover[rt]!=-1){

        cover[rt*2]=cover[rt*2+1]=cover[rt];

        l_sum[rt*2]=r_sum[rt*2]=rt_sum[rt*2]=cover[rt]?0:len-len/2;

        l_sum[rt*2+1]=r_sum[rt*2+1]=rt_sum[rt*2+1]=cover[rt]?0:len/2;

        cover[rt]=-1;

    }

}

void update(int rt,int L,int R,int flg,int l_ran,int r_ran){

    if(l_ran<=L&&R<=r_ran){ //该结点在询问区间内

        l_sum[rt]=r_sum[rt]=rt_sum[rt]= flg?0:R-L+1;

        cover[rt]=flg;

        return ;

    }

    Pushdown(rt,R-L+1); //延迟标记下移

    if(l_ran<=mid){

         update(lson,flg,l_ran,r_ran);

    }

    if(r_ran>mid){

         update(rson,flg,l_ran,r_ran);

    }

    PushUP(rt,R-L+1);   //合并出可以更长的连续区间

}

int query(int rt,int L,int R,int sum){

    if(L==R){

        return L;       //返回满足条件的区间最左端点

    }

    Pushdown(rt,R-L+1); //延迟标记向下移动

    if(rt_sum[rt*2]>=sum){

        return query(lson,sum); //左儿子的最长区间长度能满足要求

    }

    if(r_sum[rt*2]+l_sum[rt*2+1]>=sum){

            //左儿子的右端连续区间长度加右儿子的左端连续区间长度能满足要求

        return mid-r_sum[rt*2]+1;

    }

    return query(rson,sum); //询问右儿子

}

int main(){

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF){

        build(1,1,n);

        for(int i=0;i<m;i++){

            int type,st,num;

            scanf("%d",&type);

            if(type==1){

                scanf("%d",&num);

                if(rt_sum[1]<num){

                    printf("0\n");

                    continue;

                }

                st=query(1,1,n,num);

                printf("%d\n",st);

                update(1,1,n,1,st,st+num-1);

            }else{

                scanf("%d%d",&st,&num);

                update(1,1,n,0,st,st+num-1);

            }

        }

    }

    return 0;

}