#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
struct segment{
int a[1<<20],lz[1<<20][2],l0,r0;
void build(int i,int il,int ir){
lz[i][0]=lz[i][1]=-1;
if(il==ir) return;
int im=il+ir>>1;
build(i<<1,il,im), build(i<<1|1,im+1,ir);
}
void init(int l,int r){
l0=l,r0=r;
build(1,l,r);
}
void flush(int i,int il,int ir){
for(int op=0;op<2;++op){
if(lz[i][op]==-1) continue;
if(il!=ir){
if(lz[i<<1][op]==-1 || op==0&&lz[i<<1][op]<lz[i][op] || op==1&&lz[i<<1][op]>lz[i][op]) lz[i<<1][op]=lz[i][op];
if(lz[i<<1|1][op]==-1 || op==0&&lz[i<<1|1][op]<lz[i][op] || op==1&&lz[i<<1|1][op]>lz[i][op]) lz[i<<1|1][op]=lz[i][op];
}
else{
if(op==0) a[i]=max(a[i],lz[i][op]);
else a[i]=min(a[i],lz[i][op]);
}
lz[i][op]=-1;
}
}
void upd(int i,int il,int ir,int l,int r,int op,int v){
flush(i,il,ir);
if(l<=il&&ir<=r){
if(lz[i][op]==-1 || op==0&&lz[i][op]<v || op==1&&lz[i][op]>v) lz[i][op]=v, flush(i,il,ir);
return;
}
if(il>r||ir<l) return;
int im=il+ir>>1;
upd(i<<1,il,im,l,r,op,v), upd(i<<1|1,im+1,ir,l,r,op,v);
}
void upd(int l,int r,int op,int v){upd(1,l0,r0,l,r,op,v);}
int qr(int i,int il,int ir,int x){
flush(i,il,ir);
if(il==ir) return a[i];
int im=il+ir>>1;
if(x<=im) return qr(i<<1,il,im,x);
return qr(i<<1|1,im+1,ir,x);
}
int qr(int i){return qr(1,l0,r0,i);}
}t;
void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){
vector<int> comp;
for(int i=0;i<k;++i) comp.eb(L[i]),comp.eb(++R[i]);
comp.eb(0),comp.eb(n);
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
t.init(0,comp.size());
for(int i=0;i<k;++i){
L[i]=lower_bound(comp.begin(),comp.end(),L[i])-comp.begin();
R[i]=lower_bound(comp.begin(),comp.end(),R[i])-comp.begin()-1;
t.upd(L[i],R[i],op[i]-1,H[i]);
}
for(int i=0,j=0;i+1<comp.size();++i){
for(;j<comp[i+1];++j) ans[j]=t.qr(i);
}
}
