#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second
const ll mod = 998244353, maxn = 2e6 + 5, inf = 1e9 + 5;
int mi[maxn << 2], mx[maxn << 2], n, res[maxn];
pp lazy[maxn << 2];
void pull_add(int x, int k){
mi[x] = max(mi[x], k);
mx[x] = max(mx[x], k);
lazy[x].ff = max(lazy[x].ff, k);
lazy[x].ss = max(lazy[x].ss, k);
}
void pull_dec(int x, int k){
mi[x] = min(mi[x], k);
mx[x] = min(mx[x], k);
lazy[x].ff = min(lazy[x].ff, k);
lazy[x].ss = min(lazy[x].ss, k);
}
void shift(int x){
if(lazy[x].ff != -inf){
pull_add(x << 1, lazy[x].ff);
pull_add(x << 1 | 1, lazy[x].ff);
}
if(lazy[x].ss != inf){
pull_dec(x << 1, lazy[x].ss);
pull_dec(x << 1 | 1, lazy[x].ss);
}
lazy[x] = {-inf, inf};
}
void upd(int l, int r, int k, int t, int x = 1, int lx = 0, int rx = n){
if(l <= lx && r >= rx){ // t == 1 -> set_min, else -> set_max
if(t == 1){
pull_add(x, k);
}else{
pull_dec(x, k);
}
return;
} if(l >= rx || r <= lx) return;
shift(x);
int mid = (lx + rx) >> 1;
upd(l, r, k, t, x << 1, lx, mid);
upd(l, r, k, t, x << 1 | 1, mid, rx);
mi[x] = min(mi[x << 1], mi[x << 1 | 1]);
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
void get(int x = 1, int lx = 0, int rx = n){
if(lx + 1 == rx){
res[lx] = mi[x];
return;
}
shift(x);
int mid = (lx + rx) >> 1;
get(x << 1, lx, mid);
get(x << 1 | 1, mid, rx);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
::n = n;
rep(i,0,k) upd(left[i], right[i] + 1, height[i], op[i]);
get();
rep(i,0,n) finalHeight[i] = res[i];
}
