#include <bits/stdc++.h>
using namespace std;
//#define pb push_back
#define ll long long
#define endl '\n'
int sz = 1;
const int DEMO = INT_MAX, PLD = INT_MIN;
struct item{
int build = PLD, demo = DEMO;
};
struct segtree{
vector<item> arr;
vector<int> mn, mx, st;
segtree(int n){
while(sz < n)
sz *= 2;
arr.assign(2 * sz - 1, {});
mn.assign(2 * sz - 1, 0);
mx.assign(2 * sz - 1, 0);
st.assign(2 * sz - 1, -1);
}
bool tbuild(item itm){
return itm.build != PLD;
}
bool tdemo(item itm){
return itm.demo != DEMO;
}
void ass(int t, int h, item& itm){
if(!t)
itm.build = max(itm.build, h);
else
itm.demo = min(itm.demo, h);
}
void change(int t, int h, item& itm, int x){
if(!t && h >= itm.demo || t && h <= itm.build){
itm.demo = DEMO;
itm.build = PLD;
st[x] = h;
return;
}
ass(t, h, itm);
}
void min_max(int x){
if(~st[x])
mn[x] = mx[x] = st[x];
if(tbuild(arr[x])){
mn[x] = max(mn[x], arr[x].build);
mx[x] = max(mx[x], arr[x].build);
}
if(tdemo(arr[x])){
mn[x] = min(mn[x], arr[x].demo);
mx[x] = min(mx[x], arr[x].demo);
}
}
void prop(int x){
if(~st[x]){
st[2 * x + 1] = st[2 * x + 2] = st[x];
arr[2 * x + 1].build = arr[2 * x + 2].build = PLD;
arr[2 * x + 1].demo = arr[2 * x + 2].demo = DEMO;
}
if(tbuild(arr[x])){
change(0, arr[x].build, arr[2 * x + 1], 2 * x + 1);
change(0, arr[x].build, arr[2 * x + 2], 2 * x + 2);
}
if(tdemo(arr[x])){
change(1, arr[x].demo, arr[2 * x + 1], 2 * x + 1);
change(1, arr[x].demo, arr[2 * x + 2], 2 * x + 2);
}
min_max(2 * x + 1);
min_max(2 * x + 2);
st[x] = -1;
arr[x].build = PLD;
arr[x].demo = DEMO;
}
void update(int l, int r, int t, int h, int x = 0, int lx = 0, int rx = sz - 1){
if(l <= lx && rx <= r){
change(t, h, arr[x], x);
min_max(x);
return;
}
if(r < lx || rx < l){
return;
}
prop(x);
int mid = lx + rx >> 1;
update(l, r, t, h, 2 * x + 1, lx, mid);
update(l,r , t, h, 2 * x + 2, mid + 1, rx);
mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
mx[x] = max(mx[2 * x + 1], mx[2 * x + 2]);
}
int propagate(int i, int x = 0, int lx = 0, int rx = sz - 1){
if(lx == rx){
return mn[x];
}
prop(x);
int mid = lx + rx >> 1;
if(i <= mid)
return propagate(i, 2 * x + 1, lx, mid);
else
return propagate(i, 2 * x + 2, mid + 1, rx);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree st(n);
for(int i = 0; i < k; i++){
st.update(left[i], right[i], op[i] - 1, height[i]);
}
for(int i = 0; i < n; i++){
finalHeight[i] = st.propagate(i);
}
}
// void solve(){
// int k;
// cin >> n >> k;
// segtree st(n);
// while(k--){
// int t, l, r, h;
// cin >> t >> l >> r >> h;
// st.update(l, r, t - 1, h);
// }
// st.propagate();
// }
// int32_t main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// int t = 1;
// //cin >> t;
// while(t--)
// solve();
// return 0;
// }
