#include<bits/stdc++.h>
//#define name "InvMOD"
#ifndef name
#include "wall.h"
#endif // name
using namespace std;
#define fi first
#define se second
#define dbg(x) "[" << #x " = " << (x) << "]"
#define pi pair<int,int>
struct SMT{
int trsz;
vector<pi> st;
const pi base = {0, 1e9};
SMT(int n = 0): trsz(n), st((n << 2 |1)) {
for(int i = 0; i < (n << 2 | 1); i++){
st[i] = base;
}
}
void apply(int id, pi v){
st[id].fi = max(st[id].fi, v.fi);
st[id].fi = min(st[id].fi, v.se);
st[id].se = min(st[id].se, v.se);
st[id].se = max(st[id].se, v.fi);
}
void down(int id){
apply(id << 1, st[id]);
apply(id << 1|1, st[id]);
st[id] = base;
}
void update(int id, int l, int r, int u, int v, pi h){
if(l >= u && r <= v){
apply(id, h);
}
else{
int m = l+r>>1; down(id);
if(u <= m) update(id << 1, l, m, u, v, h);
if(v > m) update(id << 1|1, m+1, r, u, v, h);
}
}
int query(int id, int l, int r, int x){
if(l == r){
return st[id].fi;
}
else{
int m = l+r>>1; down(id);
if(x <= m)
return query(id << 1, l, m, x);
else return query(id << 1|1, m+1, r, x);
}
}
void upd(int l, int r, int op, int h){
if(op&1){
update(1, 0, trsz - 1, l, r, make_pair(h, 1e9));
}
else{
update(1, 0, trsz - 1, l, r, make_pair(0, h));
}
}
int get(int x){
return query(1, 0, trsz - 1, x);
}
};
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]){
SMT st(n);
for(int i = 0; i < k; i++){
st.upd(l[i], r[i], op[i], h[i]);
}
for(int i = 0; i < n; i++) fh[i] = st.get(i);
}
