#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 100, mod = 998443532, inf = 1e18;
struct str{
int mn = 0, mx = INT_MAX;
};
str t[N * 4];
void F(int v, str x){
t[v].mn = max(t[v].mn, x.mn);
t[v].mx = max(t[v].mx, t[v].mn);
t[v].mx = min(t[v].mx, x.mx);
t[v].mn = min(t[v].mn, t[v].mx);
}
void push(int v, int l, int r){
if(l != r){
F(v + v, t[v]);
F(v + v + 1, t[v]);
}
t[v] = str();
}
void upd(int v, int l, int r, int ll, int rr, str x){
if(l <= ll && rr <= r){
F(v, x);
return;
}
if(l > rr || ll > r) return;
push(v, ll, rr);
int m = (ll + rr) / 2;
upd(v + v, l, r, ll, m, x);
upd(v + v + 1, l, r, m + 1, rr, x);
}
str get(int v, int l, int r, int idx){
if(l == r){
return t[v];
}
else{
push(v, l, r);
int m = (l + r) / 2;
if(idx <= m) return get(v + v, l, m, idx);
else return get(v + v + 1, m + 1, r, idx);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]);
for(int i = 0; i < k; i++){
if(op[i] == 1){
upd(1, 0, n - 1, left[i], right[i], {height[i], INT_MAX});
}
else{
upd(1, 0, n - 1, left[i], right[i], {0, height[i]});
}
}
for(int i = 0; i < n; i++){
final_height[i] = (get(1, 0, n - 1, i)).mn;
}
}
