#include<bits/stdc++.h>
using namespace std;
#define debug(...) 40
using ll = long long;
using pii = pair<int, int>;
using db = long double;
#define int long long
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}
const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;
struct Node{
int mi = 0, mx = 1e9;
};
Node t[4 * maxn];
int ans[maxn];
void apply (int id, int mi, int mx){
if (0 <= id && id < 4 * maxn){
t[id].mi = max(t[id].mi, mi);
t[id].mx = min(t[id].mx, mx);
t[id].mi = min(t[id].mi, mx);
t[id].mx = max(t[id].mx, mi);
}
}
void update(int id, int l, int r, int u, int v, int mode, int val){
if (r < u || v < l) return;
if (u <= l && r <= v){
if (mode){
t[id].mx = min(t[id].mx, val);
t[id].mi = min(t[id].mi, val);
}
else{
t[id].mx = max(t[id].mx, val);
t[id].mi = max(t[id].mi, val);
}
return;
}
apply(id << 1, t[id].mi, t[id].mx);
apply(id << 1 | 1, t[id].mi, t[id].mx);
int mid = (l + r) / 2;
t[id] = {0, (int)1e9};
update(id << 1, l, mid, u, v, mode, val);
update(id << 1 | 1, mid + 1, r, u, v, mode, val);
}
void get(int id, int l, int r){
if (l == r){
ans[l] = min(t[id].mi, t[id].mx);
return;
}
int mid = (l + r) / 2;
apply(id << 1, t[id].mi, t[id].mx);
apply(id << 1 | 1, t[id].mi, t[id].mx);
get(id << 1, l, mid);
get(id << 1 | 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int final_height[]) {
for (int i = 0; i < k; i++) {
update(1, 0, n - 1, left[i], right[i], op[i] - 1, height[i]);
}
get(1, 0, n - 1);
for (int i = 0; i < n; i++) final_height[i] = ans[i];
}
