#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2e6 + 5, inf = 1e9;
struct node{
int l, r;
} lazy[4 * N];
void down(node &a, node b) {
if(a.l >= b.r) {
a = {b.r, b.r};
return;
}
if(a.r <= b.l) {
a = {b.l, b.l};
return;
}
a.l = max(a.l, b.l); a.r = min(a.r, b.r);
assert(a.l <= a.r);
}
void push(int u, int l,int r) {
if(lazy[u].l == 0 && lazy[u].r == inf) return;
if(l == r) return;
down(lazy[2 * u], lazy[u]);
down(lazy[2 * u + 1], lazy[u]);
lazy[u] = {0, inf};
}
void upd(int u, int st, int en, int l,int r, int v, int t) {
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
if(l == r) {
if(!t) {
lazy[u].l = max(lazy[u].l, v);
lazy[u].r = max(lazy[u].r, v);
}
else {
lazy[u].l = min(lazy[u].l, v);
lazy[u].r = min(lazy[u].r, v);
}
return;
}
if(!t) lazy[u].l = v;
else lazy[u].r = v;
push(u, l, r);
return;
}
int mid = (l + r) >> 1;
upd(2 * u, st, en, l, mid, v, t);
upd(2 * u + 1,st, en, mid + 1, r, v,t);
}
int get(int u,int ind, int l,int r){
push(u, l, r);
if(l == r) return lazy[u].l;
int mid = (l + r) / 2;
if(ind <= mid) return get(2 * u, ind, l, mid);
else return get(2 * u + 1, ind, mid + 1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ih[]){
for(int i = 1; i <= 4 * n; i++) lazy[i] = {0, inf};
--n;
for(int i = 0; i < k; i++) {
upd(1, l[i], r[i], 0, n, h[i], --op[i]);
}
for(int i = 0; i <= n; i++) {
ih[i] = get(1, i, 0, n);
}
}
