// In the name of the God
#include "wall.h"
#include <bits/stdc++.h>
// #define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e6+5;
int n, k, sl[maxn*4], sr[maxn*4], ans[maxn];
void relax(int id, int l, int r) {
int ll = sl[id], rr = sr[id];
if (max(l, ll) <= min(r, rr)) sl[id] = max(l, ll), sr[id] = min(r, rr);
else {
if (rr < l) sl[id] = sr[id] = l;
else sl[id] = sr[id] = r;
}
}
void upd(int o, int s, int e, int h, int l = 0, int r = n, int id = 1) {
if (s <= l and r <= e) {
if (o == 1) relax(id, h, inf);
else relax(id, 0, h);
return;
}
int mid = (l+r)/2;
relax(id*2, sl[id], sr[id]), relax(id*2+1, sl[id], sr[id]);
sl[id] = 0, sr[id] = inf;
if (s < mid) upd(o, s, e, h, l, mid, id*2);
if (e > mid) upd(o, s, e, h, mid, r, id*2+1);
}
void get(int l = 0, int r = n, int id = 1) {
if (l+1 == r) {
ans[l] = sl[id];
return;
}
int mid = (l+r)/2;
relax(id*2, sl[id], sr[id]), relax(id*2+1, sl[id], sr[id]);
get(l, mid, id*2), get(mid, r, id*2+1);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
n = N, k = K;
for (int i = 1; i < maxn*4; i++) sr[i] = inf;
for (int i = 0; i < k; i++) upd(op[i], left[i], right[i]+1, height[i]);
get();
for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
}
// int32_t main() {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// // buildWall();
// cin >> n >> k;
// for (int i = 1; i < maxn*4; i++) sr[i] = inf;
// for (int i = 0; i < k; i++) {
// int a, b, c, d;cin >> a >> b >> c >> d;
// upd(a, b, c+1, d);
// }
// get();
// for (int i = 0; i < n; i++) cout << ans[i] << '\n';
// return 0;
// }
