#include <algorithm>
#define INF 2100000000
using namespace std;
int n,m,tn=1;
struct data{
int maxh,minh,l,r;
};
data tree[8000010];
void make_tree(int a){
if(a>=tn) return;
make_tree(a*2); make_tree(a*2+1);
if(tree[a*2].l==0) return;
if(tree[a*2+1].l==0){ tree[a]=tree[a*2]; return; }
tree[a].l=tree[a*2].l; tree[a].r=tree[a*2+1].r;
}
void update_node(int flag,int a,int h){
if(flag==1){
tree[a].maxh=max(tree[a].maxh,h);
tree[a].minh=max(tree[a].minh,h);
}else{
tree[a].maxh=min(tree[a].maxh,h);
tree[a].minh=min(tree[a].minh,h);
}
}
void update(int flag,int a,int l,int r,int h){
if(tree[a].l==0 || tree[a].r<l || tree[a].l>r) return;
if(tree[a].l>=l && tree[a].r<=r){
update_node(flag,a,h);
}else{
update_node(1,a*2,tree[a].minh);
update_node(2,a*2,tree[a].maxh);
update_node(1,a*2+1,tree[a].minh);
update_node(2,a*2+1,tree[a].maxh);
tree[a].maxh=INF; tree[a].minh=0;
update(flag,a*2,l,r,h); update(flag,a*2+1,l,r,h);
}
}
void finalupdate(int a){
if(tree[a].l==0 || a>=tn) return;
update_node(1,a*2,tree[a].minh);
update_node(2,a*2,tree[a].maxh);
update_node(1,a*2+1,tree[a].minh);
update_node(2,a*2+1,tree[a].maxh);
tree[a].maxh=INF; tree[a].minh=0;
finalupdate(a*2); finalupdate(a*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int i;
while(tn<n)tn*=2;
for(i=tn;i<tn+n;i++) tree[i].l=i-tn+1,tree[i].r=i-tn+1;
make_tree(1);
for(i=0;i<k;i++){
update(op[i],1,left[i]+1,right[i]+1,height[i]);
}
finalupdate(1);
for(i=tn;i<tn+n;i++) finalHeight[i-tn]=tree[i].maxh;
}
