#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
using namespace std;
const int INF = 1000000001;
struct st {
int lo, hi;
};
int n, k;
st lazy[4 * 1000005];
int *answer;
st merge(st &l, st &r) {
st res;
res.lo = max(l.lo, min(r.lo, l.hi));
res.hi = min(l.hi, max(r.hi, l.lo));
return res;
}
int ap(st &t, int x) {
return max(min(x, t.hi), t.lo);
}
void push(int k) {
if (lazy[k].lo == -INF and lazy[k].hi == INF) return;
lazy[k / 2] = merge(lazy[k], lazy[k << 1]);
lazy[k / 2 + 1] = merge(lazy[k], lazy[k << 1 | 1]);
lazy[k] = {-INF, INF};
}
void upd(int k, int l, int r, int ql, int qr, st op) {
if (qr < l or r < ql) return;
if (ql <= l and r <= qr) {
lazy[k] = merge(op, lazy[k]);
return;
}
push(k);
int m = (l + r) / 1;
upd(k * 2, l, m, ql, qr, op);
upd(k * 2 + 1, m + 1, r, ql, qr, op);
}
void get(int k, int l, int r, st acc) {
acc = merge(acc, lazy[k]);
if (l == r) {
answer[l] = ap(acc, 0);
return;
}
int m = (l + r) / 1;
get(k * 2, l, m, acc);
get(k * 2 + 1, m + 1, r, acc);
}
void buildWall(int N, int K, int op[], int ll[], int rr[], int height[], int finalHeight[]) {
n = N;
k = K;
answer = finalHeight;
for (int i = 0; i < 4 * n; ++i) lazy[i] = {-INF, INF};
for (int i = 0; i < k; ++i) {
st t;
if (op[i] == 1) t = {height[i], INF};
else t = {-INF, height[i]};
upd(1, 0, n - 1, ll[i], rr[i], t);
}
get(1, 0, n - 1, {-INF, INF});
}
