#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e6+20;
const int LOG = 60;
const int MOD = 998244353;
const int SQRT = 520;
const int INF = 2e9+10;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
int n, q;
int ans[MAXN];
struct node {
int laz;
int mn, mx;
} st[4*MAXN];
struct segtree {
void merge(int id){
// mx
st[id].mx = max(st[lf].mx, st[rg].mx);
st[id].mn = min(st[lf].mn, st[rg].mn);
st[id].laz = -1;
}
void bd(int id, int l, int r){
st[id].laz = -1;
if(l==r){
st[id].mn = st[id].mx = 0;
return;
}
bd(lf, l, md); bd(rg, md+1, r);
merge(id);
}
void push(int id, int l, int r, int p){
st[id].mx = st[id].mn = p;
st[id].laz = p;
}
void bnc(int id, int l, int r){
if(l==r || st[id].laz == -1) return;
push(lf, l, md, st[id].laz);
push(rg, md+1, r, st[id].laz);
st[id].laz = -1;
}
void CHMX(int id, int l, int r, int x, int y, int p){
if(r<x || y<l || st[id].mn >= p) return;
if(x<=l && r<=y && st[id].mx <= p){ // keganti semua
push(id, l, r, p); return;
}
bnc(id, l, r);
CHMX(lf, l, md, x, y, p); CHMX(rg, md+1, r, x, y, p);
merge(id);
}
void CHMN(int id, int l, int r, int x, int y, int p){
if(r<x || y<l || st[id].mx <= p) return;
if(x<=l && r<=y && st[id].mn >= p){ // keganti semua
push(id, l, r, p); return;
}
bnc(id, l, r);
CHMN(lf, l, md, x, y, p); CHMN(rg, md+1, r, x, y, p);
merge(id);
}
void que(int id, int l, int r){
if(l==r){ ans[l] = st[id].mx; return; }
bnc(id, l, r);
que(lf, l, md); que(rg, md+1, r);
}
} A;
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
n = N;
A.bd(1, 1, n);
for(int i=0; i<k; i++){
left[i]++; right[i]++;
if(op[i]==1){ // a[i] = max(a[i], x)
A.CHMX(1, 1, n, left[i], right[i], height[i]);
} else {
A.CHMN(1, 1, n, left[i], right[i], height[i]);
}
}
A.que(1, 1, n);
for(int i=0; i<n; i++) finalHeight[i] = ans[i+1];
return;
}
