#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
using node = ll;
using lzy = pair<ll, ll>;
struct lazy{
int size;
vector<lzy> operations;
vector<node> vals;
const node NEUTRAL_ELEMENT = 0;
const lzy NO_OPERATION = {-1<<50, -1<<50};
const node START_VAL = 0;
ll query_op(node a, node b, int len, int t){
if(t==0) a=max(a, b);
else a=min(a,b);
return a;
}
ll calc_op(node a, node b){
return max(a,b);
}
void apply_mod_op(node & a, node b, int c, int t){
a = query_op(a, b, c, t);
}
void apply_mod_op(lzy&a, lzy b, int len, int t){
a.f =query_op(a.f, b.f, len, 0);
a.s =query_op(a.s, b.s, len, 1);
}
void apply_mod_op(node&a, lzy b, int len, int t){
a=query_op(a, b.f, len, 0);
a=query_op(a, b.s, len, 1);
}
void apply_mod_op(lzy&a, node b, int len, int t){
if(t==0) a.f=query_op(a.f, b, len, 0);
if(t==1) a.s=query_op(a.f, b, len, 1);
}
void propogate(int x, int lx, int rx){
if(rx - lx == 1) return;
int m = (lx + rx)/2;
apply_mod_op(operations[2*x+1], operations[x], 1, 0);
apply_mod_op(vals[2*x+1], operations[x], m-lx, 0);
apply_mod_op(operations[2*x+2], operations[x], 1, 0);
apply_mod_op(vals[2*x+2], operations[x], rx-m, 0);
operations[x] = NO_OPERATION;
}
void init(int n){
size = 1;
while(size < n) size *= 2;
operations.assign(2 * size, {-1LL<<50, 1LL<<50});
vals.assign(2 * size, 0);
}
void update(int l, int r, node v, int x, int lx, int rx, int t){
propogate(x, lx, rx);
if(lx >= r || l >= rx) return;
if(lx >= l && rx <= r){
apply_mod_op(operations[x], v, 1, t);
apply_mod_op(vals[x], v, rx - lx, t);
return;
}
int m = (lx + rx)/2;
update(l, r, v, 2 * x + 1, lx , m, t);
update(l, r, v, 2 * x + 2, m , rx, t);
vals[x] = calc_op(vals[x * 2 + 1], vals[x * 2 + 2]);
}
void update(int l, int r, ll v, int t){
update(l, r, v, 0, 0, size, t);
}
node query(int l, int r, int x, int lx, int rx){
propogate(x, lx, rx);
if(lx >= r || l >= rx) return NEUTRAL_ELEMENT;
if(lx >= l && rx <= r){
return vals[x];
}
int m = (lx + rx)/2;
node m1 = query(l, r, 2 * x + 1, lx, m);
node m2 = query(l, r, 2 * x + 2, m, rx);
return calc_op(m1, m2);
}
node query(int l , int r){
return query(l, r, 0, 0, size);
}
} st;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalheight[]){
st.init(n);
F0R(i, k){
st.update(left[i], right[i]+1, height[i], op[i]-1);
}
F0R(i, n){
finalheight[i] = st.query(i, i+1);
}
return;
}
