#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define report(x, l, s) stype[x] = s, location[x] = l, chk[x] = true
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int MAX = 2020202;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
pii tree[4*MAX];
int lazy[4*MAX];
void update_lazy(int node, int s, int e) {
if(lazy[node] == -1) return;
tree[node].fi = tree[node].se = lazy[node];
if(s != e) {
lazy[node<<1] = lazy[node<<1|1] = lazy[node];
}
lazy[node] = -1;
}
void update1(int node, int s, int e, int l, int r, int val) {
update_lazy(node, s, e);
if(s > r || e < l) return;
if(s >= l && e <= r && tree[node].fi >= val) return;
if(s >= l && e <= r && tree[node].se <= val) {
lazy[node] = val;
update_lazy(node, s, e);
return;
}
if(s == e) return;
update1(node<<1, s, s+e>>1, l, r, val);
update1(node<<1|1, (s+e>>1)+1, e, l, r, val);
tree[node].fi = min(tree[node<<1].fi, tree[node<<1|1].fi);
tree[node].se = max(tree[node<<1].se, tree[node<<1|1].se);
}
void update2(int node, int s, int e, int l, int r, int val) {
update_lazy(node, s, e);
if(s > r || e < l) return;
if(s >= l && e <= r && tree[node].se <= val) return;
if(s >= l && e <= r && tree[node].fi >= val) {
lazy[node] = val;
update_lazy(node, s, e);
return;
}
if(s == e) return;
update2(node<<1, s, s+e>>1, l, r, val);
update2(node<<1|1, (s+e>>1)+1, e, l, r, val);
tree[node].fi = min(tree[node<<1].fi, tree[node<<1|1].fi);
tree[node].se = max(tree[node<<1].se, tree[node<<1|1].se);
}
int cal(int node, int s, int e, int k) {
update_lazy(node, s, e);
if(s == e) return tree[node].fi;
if(k <= (s+e>>1)) return cal(node<<1, s, s+e>>1, k);
else return cal(node<<1|1, (s+e>>1)+1, e, k);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
for(int i = 0; i < 4 * MAX; i++) {
lazy[i] = -1;
}
for(int i = 0; i < k; i++) {
if(op[i] == 1) update1(1, 0, n-1, l[i], r[i], h[i]);
else update2(1, 0, n-1, l[i], r[i], h[i]);
}
for(int i = 0; i < n; i++) {
ans[i] = cal(1, 0, n-1, i);
}
}
