记录编号	333894	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]软件安装	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.282 s
提交时间	2016-10-31 16:21:43	内存使用	12.64 MiB

/*
	Name: [HAOI2013] 软件安装
	Copyright: 
	From：cogs1365 
	Author: Go灬Fire 
	Date: 31/10/16 16:10
	Description: 线段树维护三个参数，lm,rm,max,由线段树的性质，一个节点代表一个线段
				lm代表这个线段从左边开始可以连续使用的个数，rm代表这个线段从右边开始可以连续使用的个数
				max代表这个线段内最大的连续可以使用的个数 
				其中权值1代表可以使用，0代表已经使用
				1）建树时显然都可以使用lm=rm=max=r-l+1
				2）修改区间时如果z==1，整个区间都可以使用，否则整个区间均不能使用
				      向上传递时max是左右儿子的max与（左儿子从右端点可以连续使用的长度+右儿子从左端点可以连续使用的长度）（即左右儿子中间的部分）取较大值
					           lm分两种情况，当左儿子全部可以使用时，lm=左儿子的全部长度+右儿子的lm，rm同理
				3) 查询时一定要更新，W了千百遍
				   由于要编号最小，所以先查左儿子，左儿子不行查左右儿子中间的部分，最后查右儿子 
*/
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<ctime>
#include<cstdio>
#define LL long long
#define lson rt<<1,l,mid 
#define rson rt<<1|1,mid+1,r
#define Begin freopen("haoi13t4.in","r",stdin);freopen("haoi13t4.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=50500;
struct Node{
	int max,lazy,lm,rm;
}a[maxn<<4];
int n,m;
void Build(int rt,int l,int r){
	a[rt].lm=a[rt].rm=a[rt].max=r-l+1; 
	if(l==r)return;
	int mid=(l+r)>>1;
	Build(lson);Build(rson);
}
void Update(int rt,int l,int r){
	int z=a[rt].lazy;a[rt].lazy=0;
	a[rt<<1].lazy=a[rt<<1|1].lazy=z;
	int mid=(l+r)>>1;
	if(z==1){
		a[rt<<1].lm=a[rt<<1].rm=a[rt<<1].max=mid-l+1;
		a[rt<<1|1].lm=a[rt<<1|1].rm=a[rt<<1|1].max=r-mid;
	}
	else {
		a[rt<<1].lm=a[rt<<1].rm=a[rt<<1].max=0;
		a[rt<<1|1].lm=a[rt<<1|1].rm=a[rt<<1|1].max=0;
	}
}
void Insert(int s,int t,int z,int rt,int l,int r){
	if(s<=l && t>=r){
		if(z==1)a[rt].lm=a[rt].rm=a[rt].max=r-l+1;
		else a[rt].lm=a[rt].rm=a[rt].max=0;
		a[rt].lazy=z==1 ? 1: -1;
		return; 
	}
	if(a[rt].lazy)Update(rt,l,r);
	int mid=(l+r)>>1;
	if(s<=mid)Insert(s,t,z,lson);
	if(t>mid)Insert(s,t,z,rson);
	
	a[rt].max=max(a[rt<<1].max,a[rt<<1|1].max);
	a[rt].max=max(a[rt].max,a[rt<<1].rm+a[rt<<1|1].lm);
	if(a[rt<<1].max==mid-l+1)a[rt].lm=a[rt<<1|1].lm+a[rt<<1].max;
	else a[rt].lm=a[rt<<1].lm;
	if(a[rt<<1|1].max==r-mid)a[rt].rm=a[rt<<1].rm+a[rt<<1|1].max;
	else a[rt].rm=a[rt<<1|1].rm;
}
inline int Get_pos(int num,int rt,int l,int r){
	if(a[rt].max<num)return 0; 
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(a[rt].lazy)Update(rt,l,r);
	if(a[rt<<1].max>=num)return Get_pos(num,lson);
	if(a[rt<<1].rm+a[rt<<1|1].lm>=num)return mid-a[rt<<1].rm+1;
	if(a[rt<<1|1].max>=num)return Get_pos(num,rson);
}
void Init();
int main(){
    Begin;
    Init();
    //for(;;);
    getchar();getchar();
    End;
    return 0;
}
inline void Init(){
	scanf("%d%d",&n,&m);
	Build(1,1,n);
	for(int i=1;i<=m;i++){
		int type;scanf("%d",&type);
		if(type==2){
			int s,t;scanf("%d%d",&s,&t);t=s+t-1;
			Insert(s,t,1,1,1,n);//1代表未使用，0代表已使用 
		}
		else {
			int num;scanf("%d",&num);
			int pos=Get_pos(num,1,1,n);
			if(pos==0){printf("0\n");continue;}
			printf("%d\n",pos);
			Insert(pos,pos+num-1,0,1,1,n);
		}
	}
}