#include<bits/stdc++.h>
using namespace std;
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) forsn(i,0,n)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) dforsn(i,0,n)
#define sz(x) int(x.size())
#define all(x) begin(x),end(x)
#define pb push_back
#define fst first
#define snd second
const int INF=1e9;
typedef pair<int,int> ii;
const int SZ=1<<21;
ii st[2*SZ];
template<typename T> void chmax(T &x, T v){ if(v>x) x=v; }
template<typename T> void chmin(T &x, T v){ if(v<x) x=v; }
ii &operator+=(ii &a, ii b){
chmin(a.fst,b.fst);
chmin(a.snd,a.fst);
chmax(a.snd,b.snd);
chmax(a.fst,a.snd);
return a;
}
void pass(int u) {
if(u<SZ){
st[2*u]+=st[u],st[2*u+1]+=st[u];
st[u]={INF,0};
}
}
void update(int s, int e, ii v, int l=0, int r=SZ, int u=1){
pass(u);
if(e<=l||r<=s) return;
if(s<=l&&r<=e){
st[u]+=v;
return;
}
int m=(l+r)/2;
update(s,e,v,l,m,2*u);
update(s,e,v,m,r,2*u+1);
}
void dfs(int ans[], int n, int l=0, int r=SZ, int u=1){
pass(u);
if(r-l==1){
if(l<n) ans[l]=st[u].snd;
return;
}
int m=(l+r)/2;
dfs(ans,n,l,m,2*u);
dfs(ans,n,m,r,2*u+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
forn(u,2*SZ) st[u]={INF,0};
forn(i,k){
ii upd={INF,0};
if(op[i]==1) upd.snd=height[i];
else upd.fst=height[i];
update(left[i],right[i]+1,upd);
}
dfs(finalHeight,n);
}
