#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF=1e9+2021;
struct uwu{int type, height, time; uwu (int x, int y, int z){time=x;type=y;height=z;} };
vector<uwu> v[2<<20];
int T[2][1<<23], M[2], K;
void build (int x=1, int l=0, int r=K){
if(l==r){ T[1][x]=(!!l)*INF; return; }
build(x<<1, l, l+r>>1);
build(x<<1|1, l+r+2>>1, r);
T[1][x]=min(T[1][x<<1], T[1][x<<1|1]);
}
void upd(uwu a, int x=1, int l=0, int r=K){
if(l==r){ T[a.type][x]=a.height; return; }
int mid=l+r>>1;
if(a.time<=mid) upd(a, x<<1, l, mid);
else upd(a, x<<1|1, mid+1, r);
T[0][x]=max(T[0][x<<1], T[0][x<<1|1]);
T[1][x]=min(T[1][x<<1], T[1][x<<1|1]);
}
int get(int x=1, int l=0, int r=K){
if(l==r){
M[0]=max(M[0], T[0][x]),
M[1]=min(M[1], T[1][x]);
return (T[0][x]==M[0])?M[1]:M[0];
}
int m[]={max(M[0], T[0][x<<1|1]), min(M[1], T[1][x<<1|1])}, mid=l+r>>1;
if(m[1]>m[0]){ M[0]=m[0]; M[1]=m[1]; return get(x<<1, l, mid); }
else return get(x<<1|1, mid+1, r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
K=k; build();
for(int i=0; i<k; i++){
op[i]--;
v[left[i]].pb({i+1, op[i], height[i]});
v[right[i]+1].pb({i+1, op[i], op[i]*INF});
}
for (int i=0; i<n; i++){
for (int j=0; j<v[i].size(); j++) upd(v[i][j]);
M[0]=0; M[1]=INF; finalHeight[i]=get();
}
}
