#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ff first
#define ss second
#define sz(s) (int)s.size()
using namespace std;
const ll N = 8000002;
pair<int,int> st[N];
vector <int> v;
void lz(int nd){
if(nd * 2 < N){
st[nd*2].ff = min(st[nd].ss,st[nd*2].ff);
st[nd*2].ff = max(st[nd].ff,st[nd*2].ff);
st[nd*2].ss = min(st[nd].ss,st[nd*2].ss);
st[nd*2].ss = max(st[nd].ff,st[nd*2].ss);
}
if(nd * 2 + 1 < N){
st[nd*2+1].ff = min(st[nd].ss,st[nd*2+1].ff);
st[nd*2+1].ff = max(st[nd].ff,st[nd*2+1].ff);
st[nd*2+1].ss = min(st[nd].ss,st[nd*2+1].ss);
st[nd*2+1].ss = max(st[nd].ff,st[nd*2+1].ss);
}
return;
}
void upd(int nd, int l, int r, int x, int y, int h, int t){
lz(nd);
if(l > y or r < x) return;
if(l >= x and r <= y){
if(t == 1){
st[nd].ff = max(st[nd].ff,h);
st[nd].ss = max(st[nd].ss,h);
}
else {
st[nd].ff = min(st[nd].ff,h);
st[nd].ss = min(st[nd].ss,h);
}
return;
}
st[nd].ff = -1e9;
st[nd].ss = 1e9;
int md = (l + r) / 2;
upd(nd*2,l,md,x,y,h,t);
upd(nd*2+1,md+1,r,x,y,h,t);
}
void fnd(int nd, int l, int r){
lz(nd);
if(l == r){
v.push_back(st[nd].ff);
return;
}
int md = (l + r) / 2;
fnd(nd*2, l, md);
fnd(nd*2+1, md+1, r);
}
void buildWall(int n, int k, int t[], int l[], int r[], int h[], int a[]){
for(int i = 0; i < k; i++){
upd(1,0,n-1,l[i],r[i],h[i],t[i]);
}
fnd(1,0,n-1);
for(int i = 0; i < n; i++){
a[i] = v[i];
}
return;
}
