#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2097152;
int m[2*MAXN], mx[2*MAXN],h[2*MAXN],t[2*MAXN],lzx[MAXN*2],lzm[MAXN*2];
void push_down(int pos){
if(pos >= MAXN)return;
t[2*pos] = t[2*pos+1] = t[pos];
if(lzx[pos]){
lzx[pos] = 0; lzx[pos*2] = lzx[pos*2+1] = 1;
mx[pos*2] = min(mx[pos*2],mx[pos]);
mx[pos*2+1] = min(mx[pos*2+1],mx[pos]);
m[pos*2] = min(m[pos*2],mx[pos]);
m[pos*2+1] = min(m[pos*2+1],mx[pos]);
}
if(lzm[pos]){
lzm[pos] = 0; lzm[pos*2] = lzm[pos*2+1] = 1;
m[pos*2] = max(m[pos*2],m[pos]);
m[pos*2+1] = max(m[pos*2+1],m[pos]);
mx[pos*2] = max(mx[pos*2],m[pos]);
mx[pos*2+1] = max(mx[pos*2+1],m[pos]);
}
}
void upx(int l, int r, int ql, int qr, int n, int val){
if(l >= qr || r <= ql)return;
if(l >= ql && r <= qr){
if(val <= m[n])t[n]=1;
mx[n] = min(mx[n],val);
m[n] = min(m[n],val);
lzx[n] = 1;
return;
}
push_down(n);
upx(l,(l+r)/2,ql,qr,2*n,val);
upx((l+r)/2,r,ql,qr,2*n+1,val);
}
void upm(int l, int r, int ql, int qr, int n, int val){
if(l >= qr || r <= ql)return;
if(l >= ql && r <= qr){
if(val >= mx[n])t[n] = 0;
mx[n] = max(mx[n],val);
m[n] = max(m[n],val);
lzm[n] = 1;
return;
}
push_down(n);
upm(l,(l+r)/2,ql,qr,2*n,val);
upm((l+r)/2,r,ql,qr,2*n+1,val);
}
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
for(int i = 0; i < MAXN*2; i++)mx[i] = 1000000000;
for(int i = 0; i < k; i++){
if(op[i] == 1)upm(0,MAXN,left[i],right[i]+1,1,height[i]);
else upx(0,MAXN,left[i],right[i]+1,1,height[i]);
}
for(int i = 1; i < MAXN; i++)push_down(i);
for(int i = 0; i < n; i++){
// cout << mx[MAXN+i] << " " << m[MAXN+i]<<endl;
finalHeight[i] = m[MAXN+i];
}
}
