#include <bits/stdc++.h>
using namespace std;
const int INF = 100000;
struct dual_segment_tree_chmax{
int N;
vector<int> ST;
dual_segment_tree_chmax(vector<int> A){
int N2 = A.size();
N = 1;
while (N < N2){
N *= 2;
}
ST = vector<int>(N * 2 - 1, 0);
for (int i = 0; i < N2; i++){
ST[N - 1 + i] = A[i];
}
}
void range_chmax(int L, int R, int x, int i, int l, int r){
if (r <= L || R <= l){
return;
} else if (L <= l && r <= R){
ST[i] = max(ST[i], x);
} 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);
}
int operator [](int i){
i += N - 1;
int ans = ST[i];
while (i > 0){
i = (i - 1) / 2;
ans = max(ans, ST[i]);
}
return ans;
}
};
struct dual_segment_tree_chmin{
int N;
vector<int> ST;
dual_segment_tree_chmin(vector<int> A){
int N2 = A.size();
N = 1;
while (N < N2){
N *= 2;
}
ST = vector<int>(N * 2 - 1, INF);
for (int i = 0; i < N2; i++){
ST[N - 1 + i] = A[i];
}
}
void range_chmin(int L, int R, int x, int i, int l, int r){
if (r <= L || R <= l){
return;
} else if (L <= l && r <= R){
ST[i] = min(ST[i], x);
} 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;
int ans = ST[i];
while (i > 0){
i = (i - 1) / 2;
ans = min(ans, ST[i]);
}
return ans;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; i++){
right[i]++;
}
vector<int> A(n, 0);
dual_segment_tree_chmax ST1(A);
for (int i = 0; i < k; i++){
if (op[i] == 1){
ST1.range_chmax(left[i], right[i], height[i]);
}
}
for (int i = 0; i < n; i++){
A[i] = ST1[i];
}
dual_segment_tree_chmin ST2(A);
for (int i = 0; i < k; i++){
if (op[i] == 2){
ST2.range_chmin(left[i], right[i], height[i]);
}
}
for (int i = 0; i < n; i++){
finalHeight[i] = A[i];
}
}
