#include <bits/stdc++.h>
using namespace std;
const int MX = 2e6 + 5;
struct segtree {
int lazyMin[4 * MX], lazyMax[4 * MX], res[MX];
// each range [l, r] consider we have a bound such that elements are
// in [lazyMax, lazyMin], treat max updates as increase in lower bound
// treat min updates as decrease in upper bound
// when lazyMax = lazyMin, updates becomes equivalent to range set
void apply(int u, int v) {
// cout << "apply " << u << ' ' << v << '\n';
// cout << lazyMax[u] << " " << lazyMin[u] << '\n';
// cout << lazyMax[v] << " " << lazyMin[v] << '\n';
if(lazyMax[u] <= lazyMax[v] && lazyMin[v] <= lazyMin[u]) {
lazyMax[u] = lazyMax[v];
lazyMin[u] = lazyMin[v];
} else if(lazyMin[v] <= lazyMax[u]) {
lazyMax[u] = lazyMin[u] = lazyMin[v];
} else if(lazyMin[u] <= lazyMax[v]) {
lazyMax[u] = lazyMin[u] = lazyMax[v];
} else if(lazyMax[u] < lazyMax[v] && lazyMax[v] <= lazyMin[u] && lazyMin[u] <= lazyMin[v]) {
lazyMax[u] = lazyMax[v];
} else if(lazyMax[v] <= lazyMax[u] && lazyMax[u] <= lazyMin[v] && lazyMin[v] < lazyMin[u]) {
lazyMin[u] = lazyMin[v];
}
}
void push(int v, int l, int r) {
if(l == r) return;
if(lazyMax[v] == 0 && lazyMin[v] == 1e9) return;
apply(v * 2 + 0, v);
apply(v * 2 + 1, v);
assert(lazyMax[2 * v] <= lazyMin[2 * v]);
assert(lazyMax[2 * v + 1] <= lazyMin[2 * v + 1]);
lazyMax[v] = 0, lazyMin[v] = 1e9;
}
void minimize(int v, int l, int r, int ql, int qr, int x) {
push(v, l, r);
if(r < ql || l > qr) return;
if(ql <= l && qr >= r) {
if(lazyMax[v] > x) {
lazyMax[v] = lazyMin[v] = x;
} else if(lazyMin[v] > x) {
lazyMin[v] = x;
}
push(v, l, r);
return;
}
int m = (l + r) >> 1;
minimize(v * 2 + 0, l, m + 0, ql, qr, x);
minimize(v * 2 + 1, m + 1, r, ql, qr, x);
}
void maximize(int v, int l, int r, int ql, int qr, int x) {
push(v, l, r);
if(r < ql || l > qr) return;
if(ql <= l && qr >= r) {
if(lazyMin[v] < x) {
lazyMax[v] = lazyMin[v] = x;
} else if(lazyMax[v] < x) {
lazyMax[v] = x;
}
push(v, l, r);
return;
}
int m = (l + r) >> 1;
maximize(v * 2 + 0, l, m + 0, ql, qr, x);
maximize(v * 2 + 1, m + 1, r, ql, qr, x);
}
void get(int v, int l, int r) {
push(v, l, r);
if(l == r) {
res[l] = min(lazyMax[v], lazyMin[v]);
return;
}
int m = (l + r) >> 1;
get(v * 2 + 0, l, m + 0);
get(v * 2 + 1, m + 1, r);
}
void init() {
for(int i = 0; i < 4 * MX; i++) {
lazyMin[i] = 1e9;
}
}
} st;
void buildWall(int N, int K, int op[], int l[], int r[], int h[], int finalHeight[]) {
st.init();
for(int i = 0; i < K; i++) {
if(op[i] == 1) st.maximize(1, 0, N - 1, l[i], r[i], h[i]);
else st.minimize(1, 0, N - 1, l[i], r[i], h[i]);
}
st.get(1, 0, N - 1);
for(int i = 0; i < N; i++) {
finalHeight[i] = st.res[i];
}
}
// int op[100], l[100], r[100], h[100], N, K, f[100];
// int main() {
// cin >> N >> K;
// for(int i = 0; i < K; i++) {
// cin >> op[i] >> l[i] >> r[i] >> h[i];
// }
// buildWall(N, K, op, l, r, h, f);
// }
