#include "wall.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const ll inf = 1e18 + 10000;
const int mod = 1e9+7;
const int maxn = 2e6 + 12;
int mx[maxn * 4], mn[maxn * 4], c[maxn * 4], xl, xr, x, wt, nw;
void rlx(int v){
c[v * 2 + 1] = c[v * 2 + 2] = mn[v * 2 + 1] = mn[v * 2 + 2] = mx[v * 2 + 1] = mx[v * 2 + 2] = c[v];
c[v] = -1;
}
void upd(int v, int l, int r){
if(xr < l || r < xl)return;
if(wt == 1 && mn[v] >= x)return;
if(wt == 2 && mx[v] <= x)return;
if(xl <= l && r <= xr){
if(wt == 1 && mx[v] <= x){
mx[v] = mn[v] = x;
c[v] = x;
return;
}
if(wt == 2 && mn[v] >= x){
mn[v] = mx[v] = x;
c[v] = x;
return;
}
}
if(c[v] != -1){
rlx(v);
}
upd(v * 2 + 1, l, (l + r) / 2), upd(v * 2 + 2, (l + r) / 2 + 1, r);
mn[v] = min(mn[v * 2 + 1], mn[v * 2 + 2]), mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
int get(int v, int l, int r){
if(l == r){
return mn[v];
}
if(c[v] != -1)rlx(v);
if((l + r) / 2 < nw)return get(v * 2 + 2, (l + r) / 2 + 1, r);
else return get(v * 2 + 1, l, (l + r) / 2);
}
void buildWall(int n, int k, int op[], int left[], int right[], int h[], int fh[]){
for(int i = 0; i < n * 4; i++)c[i] = -1;
for(int i = 0; i < k; i++){
wt = op[i], xl = left[i], xr = right[i], x = h[i];
upd(0, 0, n);
}
for(int i = 0; i < n; i++){
nw = i;
fh[i] = get(0, 0, n);
}
return;
}
