#include "wall.h"
#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
const int INF = 1e9 + 1;
const int N = 2e6 + 10;
const double eps = 1e-7;
template <class T> using V = vector<T>; // from yosupo
template <class T> using VV = V<V<T>>; // from yosupo
template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
x = (x > y ? y : x);
}
struct node{
int up = 0, down = INF;
node(){}
} d[4*N];
void apply(int ind, int up, int down){
if(ind>=0&&ind<4*N){
d[ind].down = min(d[ind].down,down);
d[ind].down = max(d[ind].down,up);
d[ind].up = max(d[ind].up,up);
d[ind].up = min(d[ind].up,down);
}
}
void range_modify(int mode, int ml, int mr, int val, int ind = 1, int l = 0, int r = N-1){
if(ml>r||mr<l) return;
if(ml<=l&&mr>=r){
if(mode){
d[ind].down = min(d[ind].down,val);
d[ind].up = min(d[ind].up,val);
}
else{
d[ind].down = max(d[ind].down,val);
d[ind].up = max(d[ind].up,val);
}
return;
}
int mid = (l+r)/2;
apply(ind<<1,d[ind].up,d[ind].down);
apply(ind<<1|1,d[ind].up,d[ind].down);
d[ind].up = 0, d[ind].down = INF;
range_modify(mode,ml,mr,val,ind<<1,l,mid);
range_modify(mode,ml,mr,val,ind<<1|1,mid+1,r);
}
int n,k;
V<int> ans(n);
void query(int ind, int l, int r){
if(l==r){
if(l!=n) ans.push_back(min(d[ind].up,d[ind].down));
return;
}
apply(ind<<1,d[ind].up,d[ind].down);
apply(ind<<1|1,d[ind].up,d[ind].down);
d[ind].up = 0, d[ind].down = INF;
int mid = l+r>>1;
query(ind<<1,l,mid);
query(ind<<1|1,mid+1,r);
}
void buildWall(int X, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = X;
for(int i = 0;i < k;++i) {
op[i]--;
range_modify(op[i], left[i], right[i], height[i],1,0,n);
}
query(1,0,n);
forn(i, n) finalHeight[i] = ans[i];
//
return;
}
