#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double
#define pb push_back
struct P{
ll x, y;
};
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
#define bound array<int, 2>
const bound neutral = {0, INT_MAX};
const bound no_lazy = {-1, -1};
const int MI = 0, MA = INT_MAX;
class Segtree{
public:
int n;
vector<int> t, hi, lo; // lazy is not a bound, but an operation with 2 parameters
Segtree(int size){
n = 1;
while (n < size) n <<= 1;
t.resize(2*n);
hi.resize(2*n, MA);
lo.resize(2*n, MI);
}
void apply(int i){
t[i] = max(t[i], lo[i]);
t[i] = min(t[i], hi[i]);
hi[i] = MA;
lo[i] = MI;
}
void comb(int down, int i){
if (hi[down] <= lo[i]) lo[down] = hi[down] = lo[i];
if (lo[down] >= hi[i]) lo[down] = hi[down] = hi[i];
else{
lo[down] = max(lo[down], lo[i]);
hi[down] = min(hi[down], hi[i]);
}
}
void prop(int i){
if (lo[i] == MI && hi[i] == MA) return;
if (i >= n) apply(i);
else{
comb(2*i, i);
comb(2*i+1, i);
hi[i] = MA;
lo[i] = MI;
}
}
void update(int l, int r, int i, int a, int b, int v, int op){
prop(i);
if (b < l || r < a) return;
if (a <= l && r <= b){
if (op == 1) lo[i] = v;
else hi[i] = v;
prop(i);
return;
}
int m = (l+r)/2;
update(l, m, 2*i, a, b, v, op);
update(m+1, r, 2*i+1, a, b, v, op);
}
void update(int l, int r, int v, int op){
update(0, n-1, 1, l, r, v, op);
}
int query(int l, int r, int i, int pos){
prop(i);
assert(lo[i] == MI && hi[i] == MA);
if (l == r && l == pos) return t[i];
int m = (l+r)/2;
if (pos <= m) return query(l, m, 2*i, pos);
else return query(m+1, r, 2*i+1, pos);
}
int query(int pos){
return query(0, n-1, 1, pos);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
Segtree seg (n);
for (int i=0; i<k; i++){
seg.update(left[i], right[i], height[i], op[i]);
}
for (int i=0; i<n; i++){
finalHeight[i] = seg.query(i);
}
}
