#include <bits/stdc++.h>
#include <wall.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=2e6;
const ar<int, 2> ID={0, mxN};
int n;
ar<int, 2> st[1<<22];
ar<int, 2> app(ar<int, 2> a, ar<int, 2> b) {
a[0]=max(a[0], b[0]);
a[1]=max(a[1], b[0]);
a[0]=min(a[0], b[1]);
a[1]=min(a[1], b[1]);
return a;
}
void psh(int u) {
if (st[u]!=ID) {
st[2*u]=app(st[2*u], st[u]);
st[2*u+1]=app(st[2*u+1], st[u]);
st[u]=ID;
}
}
void upd(int ql, int qr, ar<int, 2> x, int u=1, int l=0, int r=n-1) {
if (ql<=l&&r<=qr) {
st[u]=app(st[u], x);
return;
}
psh(u);
int mid=(l+r)/2;
if (ql<=mid)
upd(ql, qr, x, 2*u, l, mid);
if (qr>mid)
upd(ql, qr, x, 2*u+1, mid+1, r);
}
void solve(int ans[], int u=1, int l=0, int r=n-1) {
if (l==r) {
assert(st[u][0]==st[u][1]);
ans[l]=st[u][0];
return;
}
int mid=(l+r)/2;
psh(u);
solve(ans, 2*u, l, mid);
solve(ans, 2*u+1, mid+1, r);
}
void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
n=_n;
for (int i=0; i<k; ++i) {
if (op[i]==1)
upd(left[i], right[i], {height[i], mxN});
else
upd(left[i], right[i], {0, height[i]});
}
solve(finalHeight);
}
/*int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int _n=10, _k=6;
int _op[6]={1, 2, 2, 1, 1, 2};
int _left[6]={1, 4, 3, 0, 2, 6};
int _right[6]={8, 9, 6, 5, 2, 7};
int _height[6]={4, 1, 5, 3, 5, 0};
int _ans[10];
buildWall(_n, _k, _op, _left, _right, _height, _ans);
for (int i=0; i<10; ++i)
cout << _ans[i] << " ";
return 0;
}*/
