#include <bits/stdc++.h>
using namespace std;
struct segment_tree {
int n;
vector<int> mn, mx;
segment_tree(int m) {
n = m;
mn.assign(n << 2, 0);
mx.assign(n << 2, 1e9);
}
void push(int v, int l, int r) {
if (l == r) return;
mn[v << 1] = min(mn[v << 1], mx[v]);
mn[v << 1 | 1] = min(mn[v << 1 | 1], mx[v]);
mx[v << 1] = min(mx[v << 1], mx[v]);
mx[v << 1 | 1] = min(mx[v << 1 | 1], mx[v]);
mn[v << 1] = max(mn[v << 1], mn[v]);
mn[v << 1 | 1] = max(mn[v << 1 | 1], mn[v]);
mx[v << 1] = max(mx[v << 1], mn[v]);
mx[v << 1 | 1] = max(mx[v << 1 | 1], mn[v]);
mx[v] = 1e9;
mn[v] = 0;
}
void qmin(int l, int r, int x, int v = 1, int tl = 0, int tr = -1) {
if (tr < 0) tr += n;
push(v, tl, tr);
if (l <= tl && tr <= r) mx[v] = x;
else {
int m = (tl + tr) >> 1;
if (l <= m) qmin(l, r, x, v << 1, tl, m);
if (m < r) qmin(l, r, x, v << 1 | 1, m + 1, tr);
}
}
void qmax(int l, int r, int x, int v = 1, int tl = 0, int tr = -1) {
if (tr < 0) tr += n;
push(v, tl, tr);
if (l <= tl && tr <= r) mn[v] = x;
else {
int m = (tl + tr) >> 1;
if (l <= m) qmax(l, r, x, v << 1, tl, m);
if (m < r) qmax(l, r, x, v << 1 | 1, m + 1, tr);
}
}
int get(int i, int v = 1, int l = 0, int r = -1) {
if (r < 0) r += n;
push(v, l, r);
if (l == r) return mn[v];
int m = (l + r) >> 1;
if (i > m) return get(i, v << 1 | 1, m + 1, r);
else return get(i, v << 1, l, m);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
segment_tree s(n);
for (int i = 0; i < k; ++i) {
if (op[i] == 1) s.qmax(left[i], right[i], height[i]);
else s.qmin(left[i], right[i], height[i]);
}
for (int i = 0; i < n; ++i) finalHeight[i] = s.get(i);
}
