#include <bits/stdc++.h>
// #include "wall.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 lzy NEUTRAL_ELEMENT = {1, infLL};
const lzy NO_OPERATION = {-69, -69};
void propogate(int x, int lx, int rx){
if(operations[x] == NO_OPERATION) return;
if(operations[x].f == 0) ckmax(vals[x], operations[x].s);
else ckmin(vals[x], operations[x].s);
if(rx - lx == 1) return;
if(operations[2*x+1].f == 0) ckmax(vals[2*x+1], operations[2*x+1].s);
else if(operations[2*x+1].f == 1)ckmin(vals[x*2+1], operations[2*x+1].s);
if(operations[2*x+2].f == 0) ckmax(vals[2*x+2], operations[2*x+2].s);
else if(operations[2*x+2].f == 1) ckmin(vals[x*2+2], operations[2*x+2].s);
operations[2*x+1] = operations[x];
operations[2*x+2] = operations[x];
operations[x] = NO_OPERATION;
}
void init(int n){
size = 1;
while(size < n) size *= 2;
operations.assign(2 * size, NO_OPERATION);
vals.assign(2 * size, 0);
// build(0, 0, size);
}
void update(int l, int r, lzy v, int x, int lx, int rx){
propogate(x, lx, rx);
if(lx >= r || l >= rx) return;
if(lx >= l && rx <= r){
operations[x] = v;
propogate(x, lx, rx);
return;
}
int m = (lx + rx)/2;
update(l, r, v, 2 * x + 1, lx , m);
update(l, r, v, 2 * x + 2, m , rx);
}
void update(int l, int r, lzy v){
update(l, r, v, 0, 0, size);
}
node query(int l, int x, int lx, int rx){
propogate(x, lx, rx);
if(lx + 1 == rx){
assert(lx == l);
return vals[x];
}
int m = (lx + rx)/2;
if(l < m)
return query(l, 2 * x + 1, lx, m);
else
return query(l, 2 * x + 2, m, rx);
}
node query(int r){
return query(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, {op[i]-1, height[i]});
// F0R(j, n){
// cout << st.query(j, j + 1) << nl;
// }
// cout << "NEW\n";
}
F0R(i, n){
finalheight[i] = st.query(i);
}
return;
}
// int main(){
// int n, k;
// cin >> n >> k;
// vi op(k), left(k), right(k), height(k), finalheight(n, 0);
// F0R(i, k) {
// cin >> left[i] >> right[i] >> height[i] >> op[i];
// }
// buildWall(n, k, op, left, right, height, finalheight);
// F0R(i, n){
// cout << finalheight[i] << " ";
// }
// }
