#include <bits/stdc++.h>
typedef long long int ll;
#define INF ll(1e9 + 7)
#define INF2 998244353
#define N (ll)(1e5 + 5)
using namespace std;
//#define int ll
#define lsb(x) (x & (-x))
int n, g, h,m, q,z,t1,t2, ans=0, ans2, n2, k, n3;
int comb(int x, int y){
return max(x, y);
}
struct SegTree{
int n;
vector<int> tree, tmax, tmin;
SegTree(int _n){
n = _n+1;
while(lsb(n) != n)
n += lsb(n);
tree.resize(2*n, 0);
tmax.resize(2*n, 0);
tmin.resize(2*n, INF);
}
void update(int i, int val){
i += n;
tree[i] = val;
while(i >>= 1){
tree[i] = comb(tree[i * 2] , tree[i * 2 | 1]);
}
}
void push(int i, int len){
if(!len)return;
if(tmin[i] != INF){
tmin[i * 2 + 1] = tmin[i * 2] = tmin[i];
tree[i * 2 + 1] = min(tmin[i], tree[i * 2 + 1]);
tree[i * 2] = min(tmin[i], tree[i * 2]);
tmin[i] = INF;
}
if(tmax[i]){
tmax[i * 2 + 1] = tmax[i * 2] = tmax[i];
tree[i * 2 + 1] = max(tmax[i], tree[i * 2 + 1]);
tree[i * 2] = max(tmax[i], tree[i * 2]);
tmax[i] = 0;
}
}
void maxx(int v, int ql, int qr){maxx(1, v, 0, n - 1, ql, qr);}
void maxx(int i, int v, int lb, int rb, int ql, int qr){
if(lb > qr || rb < ql)return;
if(ql <= lb && rb <= qr){
if(tmin[i] != INF)tmin[i] = INF;
tmax[i] = max(tmax[i], v);
tree[i] = max(tree[i], v);
return;
}
int md = (rb + lb) /2;
push(i, rb - lb + 1);
maxx(i * 2, v, lb, md, ql, qr);
maxx(i * 2 + 1, v, md + 1, rb, ql, qr);
//tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
void minn(int v, int ql, int qr){minn(1, v, 0, n - 1, ql, qr);}
void minn(int i, int v, int lb, int rb, int ql, int qr){
if(lb > qr || rb < ql)return;
if(ql <= lb && rb <= qr){
if(tmax[i])tmax[i] = 0;
tmin[i] = min(tmin[i], v);
tree[i] = min(tree[i], v);
return;
}
int md = (rb + lb) /2;
push(i, rb - lb + 1);
minn(i * 2, v, lb, md, ql, qr);
minn(i * 2 + 1, v, md + 1, rb, ql, qr);
//tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
int qu(int ql, int qr){return qu(1, 0, n - 1, ql, qr);}
int qu(int i, int lb, int rb, int ql, int qr){
if(lb > qr || rb < ql)return - 1;
if(ql <= lb && rb <= qr){
return tree[i];
}
int md = (rb + lb) /2;
push(i, rb - lb + 1);
return max(qu(i * 2, lb, md, ql, qr), qu(i * 2 + 1, md + 1, rb, ql, qr));
//tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
};
void buildWall(int n, int k, int op[], int le[], int ri[], int height[], int finalHeight[]){
SegTree s(n + 1);
for(int i=0; i<k; i++){
if(op[i] == 1){
s.maxx(height[i], le[i], ri[i]);
}
else{
s.minn(height[i], le[i], ri[i]);
}
}
for(int i=0; i<n; i++){
finalHeight[i] = s.qu(i, i);
}
}
