#include <bits/stdc++.h>
#define ll int
#define AI ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define oo 1e18
using namespace std;
const int sz = 2e6;
struct node {
ll lzmi;
ll lzma;
node() : lzmi(0), lzma(1e9) {}
};
ll v[sz];
node lz[sz*4];
ll ql, qr, t, x;
void relax(ll pos, ll l, ll r) {
ll mi = lz[pos].lzmi;
ll ma = lz[pos].lzma;
lz[pos].lzmi = 0;
lz[pos].lzma = 1e9;
if (l == r) {
if (v[l] < mi) v[l] = mi;
else if (v[l] > ma) v[l] = ma;
return;
}
if (mi != 0) {
lz[pos*2+1].lzmi = max(mi, lz[pos*2+1].lzmi);
lz[pos*2+2].lzmi = max(mi, lz[pos*2+2].lzmi);
}
if (ma != 1e9) {
lz[pos*2+1].lzma = min(ma, lz[pos*2+1].lzma);
lz[pos*2+2].lzma = min(ma, lz[pos*2+2].lzma);
}
mi = lz[pos*2+1].lzmi;
ma = lz[pos*2+1].lzma;
lz[pos*2+1].lzmi = min(mi, ma);
lz[pos*2+1].lzma = max(mi, ma);
mi = lz[pos*2+2].lzmi;
ma = lz[pos*2+2].lzma;
lz[pos*2+2].lzmi = min(mi, ma);
lz[pos*2+2].lzma = max(mi, ma);
}
void upd(ll l, ll r, ll pos) {
relax(pos, l, r);
if (ql > r || l > qr) return;
if (ql <= l && r <= qr) {
if (t == 1) { // add operation
lz[pos].lzmi = max(lz[pos].lzmi, x);
if (lz[pos].lzma < lz[pos].lzmi)
lz[pos].lzma = lz[pos].lzmi;
} else { // min operation
lz[pos].lzma = min(x, lz[pos].lzma);
if (lz[pos].lzmi > lz[pos].lzma)
lz[pos].lzmi = lz[pos].lzma;
}
relax(pos, l, r);
return;
}
ll mid = (l + r) / 2;
upd(l, mid, pos*2+1);
upd(mid+1, r, pos*2+2);
}
void build(ll l, ll r, ll pos) {
relax(pos, l, r);
if (l == r) return;
ll mid = (l + r) / 2;
build(l, mid, pos*2+1);
build(mid+1, r, pos*2+2);
}
void buildWall(ll n, ll k, ll op[], ll left[], ll right[], ll height[], ll finalHeight[]) {
memset(v, 0, sizeof(v)); // Ensure array is initialized
for (ll i = 0; i < k; i++) {
t = op[i];
ql = left[i];
qr = right[i];
x = height[i];
upd(0, n - 1, 0);
}
build(0, n - 1, 0);
for (ll i = 0; i < n; i++) finalHeight[i] = v[i];
}
/*
int main() {
AI
ll n, k;
cin >> n >> k;
ll v1[k], v2[k], v3[k], v4[k];
ll v5[n];
for (ll i = 0; i < k; i++) {
cin >> v1[i] >> v2[i] >> v3[i] >> v4[i];
}
buildWall(n, k, v1, v2, v3, v4, v5);
for (ll i = 0; i < n; i++) {
cout << v5[i] << ' ';
}
cout << endl;
return 0;
}
*/
