/// hhoangcpascal
#include <cstdio>
#include <iostream>
#include <algorithm>
#define file_name "WALL"
using namespace std;
struct node {
int mmin, mmax;
} Seg[8000006];
void update(int id, int val, int type) {
if (type == 2) {
Seg[id].mmax = min(Seg[id].mmax, val);
Seg[id].mmin = min(Seg[id].mmin, val);
} else {
Seg[id].mmax = max(Seg[id].mmax, val);
Seg[id].mmin = max(Seg[id].mmin, val);
}
}
void down(int id) {
Seg[id<<1].mmax = max(min(Seg[id<<1].mmax, Seg[id].mmax), Seg[id].mmin);
Seg[id<<1].mmin = min(max(Seg[id<<1].mmin, Seg[id].mmin), Seg[id].mmax);
Seg[id<<1|1].mmax = max(min(Seg[id<<1|1].mmax, Seg[id].mmax), Seg[id].mmin);
Seg[id<<1|1].mmin = min(max(Seg[id<<1|1].mmin, Seg[id].mmin), Seg[id].mmax);
Seg[id].mmax = 1e9, Seg[id].mmin = 0;
}
void update(int id, int l, int r, int u, int v, int val, int type) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
update(id, val, type);
return;
}
int mid = (l + r) >> 1;
down(id);
update(id<<1, l, mid, u, v, val, type);
update(id<<1|1, mid+1, r, u, v, val, type);
}
int ans[2000006];
void cal(int id, int l, int r) {
if (l > r) return;
if (l == r) {
ans[l] = Seg[id].mmin;
return;
}
int mid = (l + r) >> 1;
down(id);
cal(id<<1, l, mid);
cal(id<<1|1, mid+1, r);
}
void buildWall(int n, int k, int op[], int Left[], int Right[], int height[], int finalHeight[]) {
for(int i=0; i<k; ++i)
update(1, 1, n, Left[i]+1, Right[i]+1, height[i], op[i]);
cal(1, 1, n);
for(int i=0; i<n; ++i) finalHeight[i] = ans[i+1];
}
