#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const ll MX = 1e10;
struct segtree {
vector<ll> mni, mxi;
ll n;
segtree(ll _n) {
n = _n;
mni = vector<ll>(4 * n, 0);
mxi = vector<ll>(4 * n, MX);
}
void prop(ll i, ll l, ll r, ll mn, ll mx) {
mni[i] = min(max(mni[i], mn), mx);
mxi[i] = min(max(mxi[i], mn), mx);
}
void chk(ll i, ll l, ll r) {
if (l == r)return;
prop(i * 2, l, (l + r) / 2, mni[i], mxi[i]);
prop(i * 2 + 1, (l + r) / 2 + 1, r, mni[i], mxi[i]);
}
void updateMAX(ll i, ll l, ll r, ll ql, ll qr, ll val) {
if (r < ql or l > qr)return;
if (ql <= l and r <= qr) {
mni[i] = max(mni[i], val);
mxi[i] = max(mxi[i], val);
return;
}
chk(i, l, r);
updateMAX(i * 2, l, (l + r) / 2, ql, qr, val);
updateMAX(i * 2 + 1, (l + r) / 2 + 1, r, ql, qr, val);
mni[i] = min(mni[i * 2], mni[i * 2 + 1]);
mxi[i] = max(mxi[i * 2], mxi[i * 2 + 1]);
}
void updateMIN(ll i, ll l, ll r, ll ql, ll qr, ll val) {
if (r < ql or l > qr)return;
if (ql <= l and r <= qr) {
mni[i] = min(mni[i], val);
mxi[i] = min(mxi[i], val);
return;
}
chk(i, l, r);
updateMIN(i * 2, l, (l + r) / 2, ql, qr, val);
updateMIN(i * 2 + 1, (l + r) / 2 + 1, r, ql, qr, val);
mni[i] = min(mni[i * 2], mni[i * 2 + 1]);
mxi[i] = max(mxi[i * 2], mxi[i * 2 + 1]);
}
void get(ll i, ll l, ll r, vector<ll> &x) {
if (l == r) {
x[l] = mni[i];
return;
}
chk(i, l, r);
get(i * 2, l, (l + r) / 2, x);
get(i * 2 + 1, (l + r) / 2 + 1, r, x);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
segtree seg(n);
for (ll i = 0; i < k; i++) {
ll l = left[i], r = right[i], v = height[i], ops = op[i];
if (ops == 1)seg.updateMAX(1, 0, n - 1, l, r, v);
else seg.updateMIN(1, 0, n - 1, l, r, v);
}
vector<ll> x(n);
seg.get(1, 0, n - 1, x);
for (ll i = 0; i < n; i++)finalHeight[i] = x[i];
}
// int main() {
// int n, k;
// cin >> n >> k;
// int op[k], left[k], right[k], height[k], finalheight[n];
// for (int i = 0; i < k; i++) cin >> op[i] >> left[i] >> right[i] >> height[i];
// buildWall(n, k, op, left, right, height, finalheight);
// for (int i = 0; i < n; i++) cout << finalheight[i] << ' ';
// }
