#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 (l <= ql and qr <= r) {
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 (l <= ql and qr <= r) {
mni[i] = min(mni[i], val);
mxi[i] = min(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 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, start, d;
// cin >> n >> start >> d;
// int arr[n];
// for (ll i = 0; i < n; i++)cin >> arr[i];
// cout << findMaxAttraction(n, start, d, arr);
// return 0;
// }
