#include <wall.h>
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e6+5;
int t[MXN*4], lo[MXN*4], hi[MXN*4];
const int inf = 1e9;
void push(int x,int s,int e){
if(s!=e){
if(lo[x]!=-1e9) {
lo[x*2] = max(lo[x*2],lo[x]);
hi[x*2] = max(hi[x*2],lo[x]);
lo[x*2+1] = max(lo[x*2+1],lo[x]);
hi[x*2+1] = max(hi[x*2+1],lo[x]);
}
if(hi[x]!=1e9){
lo[x*2] = min(lo[x*2],hi[x]);
hi[x*2] = min(hi[x*2],hi[x]);
lo[x*2+1] = min(lo[x*2+1],hi[x]);
hi[x*2+1] = min(hi[x*2+1],hi[x]);
}
}
else {
t[x] = max(t[x],lo[x]);
t[x] = min(t[x],hi[x]);
}
lo[x] = -1e9;
hi[x] = 1e9;
}
void upd(int x,int s,int e,int l,int r,int v,int t){
push(x,s,e);
if(e<l || r<s) return;
if(l<=s && e<=r) {
if(t==1) lo[x] = v;
else hi[x] = v;
return push(x,s,e);
}
int mid = s+e>>1;
upd(x*2,s,mid,l,r,v,t), upd(x*2+1,mid+1,e,l,r,v,t);
}
int get(int x,int s,int e,int p){
push(x,s,e);
if(s==e) return x;
int mid = s+e>>1;
if(p<=mid) return get(x*2,s,mid,p);
return get(x*2+1,mid+1,e,p);
}
void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 1;i<=4*n;i++) lo[i] = -1e9, hi[i] = 1e9;
upd(1,0,n-1,0,n-1,0,1);
upd(1,0,n-1,0,n-1,0,2);
for(int i = 0;i<q;i++){
int t,l,r,v;
t = op[i];
l = left[i];
r = right[i];
v = height[i];
upd(1,0,n-1,l,r,v,t);
}
for(int i = 0;i<n;i++){
int x = get(1,0,n-1,i);
finalHeight[i] = t[x];
}
}
