#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define sp << ' ' <<
#define nl << '\n'
#include "wall.h"
const int INF = 1e18;
struct SegmentTree{
using T = array<int, 2>;
vector<T> a;
int sz = 1;
T ID = {0, INF};
SegmentTree(int n){
while(sz < n) sz += sz;
a.assign(2*sz, ID);
}
void apply(T &x, T &y){
y[0] = max(y[0], x[0]);
y[1] = max(y[1], x[0]);
y[0] = min(y[0], x[1]);
y[1] = min(y[1], x[1]);
}
void push(int x){
if(a[x] == ID) return;
if(x+1<sz){
apply(a[x], a[2*x+1]);
apply(a[x], a[2*x+2]);
a[x] = ID;
}
}
void update(int l, int r, T v, int x, int lx, int rx){
push(x);
if(r<=lx or rx<=l) return;
if(l<=lx and rx<=r) return apply(v, a[x]);
int mx = (lx+rx)/2;
update(l, r, v, 2*x+1, lx, mx);
update(l, r, v, 2*x+2, mx, rx);
}
void update(int l, int r, int low, int high){
T v = {low, high};
update(l, r+1, v, 0, 0, sz);
}
void build(vector<int> &ans, int n, int x, int lx, int rx){
push(x);
if(rx-lx==1){
// cout << a[x][0] nl;
if(lx<n) ans[lx] = a[x][0];
return;
}
int mx = (lx+rx)/2;
build(ans, n, 2*x+1, lx, mx);
build(ans, n, 2*x+2, mx, rx);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegmentTree st(n);
for(int i=0; i<k; ++i){
// cout << op[i] sp left[i] sp right[i] sp height[i] nl;
if(op[i]==1) st.update(left[i], right[i], height[i], INF);
else st.update(left[i], right[i], 0, height[i]);
}
vector<int> ans(n);
st.build(ans, n, 0, 0, st.sz);
for(int i=0; i<n; ++i) finalHeight[i] = ans[i];
}
