#include <bits/stdc++.h>
using namespace std;
const int INF = 100000;
struct monoid{
int mn, mx;
monoid(): mn(0), mx(INF){
}
monoid(int mn, int mx): mn(mn), mx(mx){
}
};
monoid f(monoid A, monoid B){
if (B.mx < A.mn){
B.mn = A.mn;
B.mx = A.mn;
} else if (B.mn > A.mx){
B.mn = A.mx;
B.mx = A.mx;
} else {
B.mn = max(B.mn, A.mn);
B.mx = min(B.mx, A.mx);
}
return B;
}
struct dual_segment_tree{
int N;
vector<monoid> ST;
dual_segment_tree(int N2){
N = 1;
while (N < N2){
N *= 2;
}
ST = vector<monoid>(N * 2 - 1);
for (int i = 0; i < N2; i++){
ST[N - 1 + i] = monoid(0, 0);
}
}
void eval(int i){
if (i < N - 1){
ST[i * 2 + 1] = f(ST[i], ST[i * 2 + 1]);
ST[i * 2 + 2] = f(ST[i], ST[i * 2 + 2]);
ST[i] = monoid();
}
}
void range_chmax(int L, int R, int x, int i, int l, int r){
eval(i);
if (r <= L || R <= l){
return;
} else if (L <= l && r <= R){
ST[i] = f(monoid(x, INF), ST[i]);
} else {
int m = (l + r) / 2;
range_chmax(L, R, x, i * 2 + 1, l, m);
range_chmax(L, R, x, i * 2 + 2, m, r);
}
}
void range_chmax(int L, int R, int x){
range_chmax(L, R, x, 0, 0, N);
}
void range_chmin(int L, int R, int x, int i, int l, int r){
eval(i);
if (r <= L || R <= l){
return;
} else if (L <= l && r <= R){
ST[i] = f(monoid(0, x), ST[i]);
} else {
int m = (l + r) / 2;
range_chmin(L, R, x, i * 2 + 1, l, m);
range_chmin(L, R, x, i * 2 + 2, m, r);
}
}
void range_chmin(int L, int R, int x){
range_chmin(L, R, x, 0, 0, N);
}
int operator [](int i){
i += N - 1;
monoid ans = ST[i];
while (i > 0){
i = (i - 1) / 2;
ans = f(ST[i], ans);
}
assert(ans.mn == ans.mx);
return ans.mn;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
dual_segment_tree ST(n);
for (int i = 0; i < k; i++){
right[i]++;
if (op[i] == 1){
ST.range_chmax(left[i], right[i], height[i]);
}
if (op[i] == 2){
ST.range_chmin(left[i], right[i], height[i]);
}
}
for (int i = 0; i < n; i++){
finalHeight[i] = ST[i];
}
}
