#include<bits/stdc++.h>
using namespace std;
int mn[8000005],mx[8000005];
void pushdown(int o){
	mn[o<<1]=max(mn[o<<1],mx[o]);
	mx[o<<1]=max(mx[o<<1],mx[o]);
	mn[o<<1]=min(mn[o<<1],mn[o]);
	mx[o<<1]=min(mx[o<<1],mn[o]);
	mn[o<<1|1]=max(mn[o<<1|1],mx[o]);
	mx[o<<1|1]=max(mx[o<<1|1],mx[o]);
	mn[o<<1|1]=min(mn[o<<1|1],mn[o]);
	mx[o<<1|1]=min(mx[o<<1|1],mn[o]);
	mx[o]=0,mn[o]=1.1e9;
}
void r1(int l,int r,int o,int ll,int rr,int h){
	if(l>=ll&&r<=rr){
		mn[o]=max(mn[o],h);
		mx[o]=max(mx[o],h);
		return;
	}
	pushdown(o);
	int mid=(l+r)>>1;
	if(mid>=ll)r1(l,mid,o<<1,ll,rr,h);
	if(mid<rr)r1(mid+1,r,o<<1|1,ll,rr,h);
}
void r2(int l,int r,int o,int ll,int rr,int h){
	if(l>=ll&&r<=rr){
		mn[o]=min(mn[o],h);
		mx[o]=min(mx[o],h);
		return;
	}
	pushdown(o);
	int mid=(l+r)>>1;
	if(mid>=ll)r2(l,mid,o<<1,ll,rr,h);
	if(mid<rr)r2(mid+1,r,o<<1|1,ll,rr,h);
}
int tot;
int ans[2000005];
void output(int l,int r,int o){
	if(l==r){
		ans[tot++]=mx[o];
		return;
	}
	pushdown(o);
	int mid=(l+r)>>1;
	output(l,mid,o<<1);
	output(mid+1,r,o<<1|1);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	for(int i=1;i<=4*n;++i)mx[i]=0,mn[i]=1.1e9;
	for(int i=0;i<k;++i){
		if(op[i]==1)r1(0,n-1,1,left[i],right[i],height[i]);
		else r2(0,n-1,1,left[i],right[i],height[i]);
	}
	tot=0;
	output(0,n-1,1);
	for(int i=0;i<n;++i)finalHeight[i]=ans[i];
}