#include <bits/stdc++.h>
#include <wall.h>
#define PB push_back
#define ST first
#define ND second
//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
const int INF = 2e9 + 10;
int n, k;
struct Node {
int h, H;
void eval(Node &u) {
h = max(h, u.h);
if(h > H) H = h;
H = min(H, u.H);
if(h > H) h = H;
}
};
Node T[(1 << 22)];
void prop(int x) {
T[2*x].eval(T[x]);
T[2*x+1].eval(T[x]);
T[x] = {-INF, INF};
}
void init(int l, int r, int v) {
T[v].h = -INF; T[v].H = INF;
if(l == r) return;
int mid = (l + r)/2;
init(l,mid,v*2);
init(mid+1,r,v*2+1);
}
void tree(int l, int r, int v) {
cout << l << " " << r << ": " << T[v].h << " " << T[v].H << "\n";
if(l==r) return;
tree(l,(l+r)/2,v*2);
tree((l+r)/2+1,r,v*2+1);
}
void upd(int a, int b, int l, int r, int v, Node u) {
if(a <= l && r <= b) {
T[v].eval(u);
return;
}
prop(v);
int mid = (l + r) / 2;
if(a <= mid) upd(a,b,l,mid,v*2,u);
if(mid < b) upd(a,b,mid+1,r,v*2+1,u);
}
int res[2'000'000 + 10];
void rec(int l, int r, int v) {
if(l == r) {
res[l] = min(max(T[v].h, 0), T[v].H);
return;
}
prop(v);
int mid = (l+r)/2;
rec(l,mid,v*2);
rec(mid+1,r,v*2+1);
}
void buildWall(int _n, int _k, int op[], int l[], int r[], int hei[], int ans[]) {
n = _n; k = _k;
init(0, n-1, 1);
for(int i = 0; i < k; ++i) {
if(op[i]-1) {
upd(l[i], r[i], 0, n-1, 1, {-INF, hei[i]});
} else {
upd(l[i], r[i], 0, n-1, 1, {hei[i], INF});
}
//tree(0,n-1,1);
//cout << "-----\n";
}
rec(0,n-1,1);
//tree(0,n-1,1);
//cout << "----\n";
for(int i = 0; i < n; ++i) {
ans[i] = res[i];
//cout << ans[i] << " ";
}
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//cin >> n >> k;
//int op[k], l[k], r[k], hei[k], ans[n];
//for(int i = 0; i < k; ++i) {
//cin >> op[i] >> l[i] >> r[i] >> hei[i];
//}
//buildWall(n,k,op,l,r,hei,ans);
//}
