#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;
struct Node{
ll mn, mx, lzset;
Node(ll a = 0, ll b = 0, ll c = -1) : mn(a), mx(b), lzset(c) {}
Node operator + (Node other){
ll cmn = min(mn, other.mn);
ll cmx = max(mx, other.mx);
return Node(cmn, cmx);
}
};
Node seg[4 * MAX];
void refresh(ll p, ll l, ll r){
if(seg[p].lzset == -1) return;
ll st = seg[p].lzset;
seg[p].lzset = -1;
seg[p].mn = st;
seg[p].mx = st;
if(l == r) return;
ll e = 2 * p, d = e + 1;
seg[e].lzset = st;
seg[d].lzset = st;
}
void update(ll a, ll b, ll x, ll p, ll l, ll r, bool type){
refresh(p, l, r);
if(a > r || b < l) return;
bool change = (type ? (seg[p].mx < x) : (seg[p].mn > x));
if(l == r && !change) return;
if(a <= l && r <= b && change){
seg[p].lzset = x;
refresh(p, l, r);
return;
}
ll m = (l + r) >> 1, e = 2 * p, d = e + 1;
update(a, b, x, e, l, m, type); update(a, b, x, d, m + 1, r, type);
seg[p] = seg[e] + seg[d];
}
ll getVal(ll i, ll p, ll l, ll r){
refresh(p, l, r);
if(l == r) return seg[p].mn;
ll m = (l + r) >> 1, e = 2 * p, d = e + 1;
refresh(e, l, m); refresh(d, m + 1, r);
if(i <= m) return getVal(i, e, l, m);
return getVal(i, d, m + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; i++){
ll l = left[i] + 1, r = right[i] + 1, h = height[i];
if(op[i] == 1) update(l, r, h, 1, 1, n, 1);
else update(l, r, h, 1, 1, n, 0);
}
for(int i = 0; i < n; i++)
finalHeight[i] = getVal(i + 1, 1, 1, n);
}
