#include "bits/stdc++.h"
#include "wall.h"
using namespace std;
const int N = 2e6 + 5;
const int INF = 1e9 + 5;
array<int,2> seg[4*N];
inline array<int,2> apply(array<int,2> a,array<int,2> b){
if(a[0] > a[1]) return b;
if(b[0] > a[1]) return {b[0],b[0]};
if(b[1] < a[0]) return {b[1],b[1]};
return {max(b[0],a[0]),min(b[1],a[1])};
}
inline void push(int rt,int l,int r){
if(l == r) return;
if(seg[rt][0] == 1 && seg[rt][1] == 0) return;
array<int,2> u = seg[rt];
seg[rt][0] = 1, seg[rt][1] = 0;
seg[rt*2] = apply(seg[rt*2], u);
seg[rt*2+1] = apply(seg[rt*2+1], u);
}
void upd(int rt,int l,int r,int gl,int gr,array<int,2> u){
push(rt,l,r);
if(r<gl || l>gr) return;
if(l>=gl && r<=gr){
seg[rt]=apply(seg[rt],u);
push(rt,l,r);
return;
}
int m=(l+r)/2;
upd(rt*2,l,m,gl,gr,u),upd(rt*2+1,m+1,r,gl,gr,u);
}
array<int,2> query(int rt,int l,int r,int ind){
push(rt,l,r);
if(l==r) return seg[rt];
int m=(l+r)/2;
if(ind<=m) return query(rt*2,l,m,ind);
return query(rt*2+1,m+1,r,ind);
}
void buildWall(int _n, int _q, int _op[], int left[], int right[], int height[], int finalHeight[]){
int n=_n,q=_q;
int ar[n+5];
for(int i=1;i<=n;i++) ar[i]=0;
for(int i=0;i<4*N;i++) seg[i]={1,0};
for(int i=0;i<q;i++){
int op=_op[i],l=left[i]+1,r=right[i]+1,h=height[i];
if(op==1) upd(1,1,n,l,r,{h,INF});
else upd(1,1,n,l,r,{-INF,h});
}
for(int i=1;i<=n;i++){
auto x = query(1,1,n,i);
if(x[0] == 1 && x[1] == 0) finalHeight[i-1]=0;
else if(ar[i] <= x[0]) finalHeight[i-1]=x[0];
else if(ar[i] <= x[1]) finalHeight[i-1]=0;
else finalHeight[i-1]=x[1];
}
return;
}
/*void _(){
int n,q;
cin >> n >> q;
int ar[n+5];
for(int i=1;i<=n;i++) ar[i]=0;
for(int i=0;i<4*N;i++) seg[i]={1,0};
for(int i=1;i<=q;i++){
int op,l,r,h;
cin >> op >> l >> r >> h;
if(op==1) upd(1,1,n,l,r,{h,INF});
else upd(1,1,n,l,r,{-INF,h});
}
for(int i=1;i<=n;i++){
auto x = query(1,1,n,i);
if(x[0] == 1 && x[1] == 0) cout << 0 << '\n';
else if(ar[i] <= x[0]) cout << x[0] << '\n';
else if(ar[i] <= x[1]) cout << ar[i] << '\n';
else cout << x[1] << '\n';
}
}
int32_t main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc=1;//cin >> tc;
while(tc--) _();
}*/
