#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
struct IT {
vector<int> lo, hi;
IT (int sz) : lo(4 * sz), hi(4 * sz) {}
void applyRange (int k, int fL, int fR) {
lo[k] = max(lo[k], fL), hi[k] = max(hi[k], fL);
lo[k] = min(lo[k], fR), hi[k] = min(hi[k], fR);
}
void pushDown (int k) {
applyRange(2 * k, lo[k], hi[k]), applyRange(2 * k + 1, lo[k], hi[k]);
}
void update (int a, int b, int fL, int fR, int k, int l, int r) {
if (b < l || r < a) return;
if (a <= l && r <= b)
return applyRange(k, fL, fR), void();
pushDown(k);
int mid = (l + r) >> 1;
update(a, b, fL, fR, 2 * k, l, mid);
update(a, b, fL, fR, 2 * k + 1, mid + 1, r);
lo[k] = min(lo[2 * k], lo[2 * k + 1]), hi[k] = max(hi[2 * k], hi[2 * k + 1]);
}
void dfsPrint (int k, int l, int r, int finalHeight[]) {
if (l == r) {
assert(lo[k] == hi[k]);
return finalHeight[l] = lo[k], void();
}
pushDown(k);
int mid = (l + r) >> 1;
dfsPrint(2 * k, l, mid, finalHeight);
dfsPrint(2 * k + 1, mid + 1, r, finalHeight);
lo[k] = min(lo[2 * k], lo[2 * k + 1]), hi[k] = max(hi[2 * k], hi[2 * k + 1]);
}
};
void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
IT tree(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) tree.update(left[i], right[i], height[i], INT_MAX, 1, 0, n - 1);
if (op[i] == 2) tree.update(left[i], right[i], INT_MIN, height[i], 1, 0, n - 1);
}
tree.dfsPrint(1, 0, n - 1, finalHeight);
}
#ifdef LOCAL
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int op[] = {1, 2, 2, 1, 1, 2}, left[] = {1, 4, 3, 0, 2, 6}, right[] = {8, 9, 6, 5, 2, 7};
int height[] = {4, 1, 5, 3, 5, 0}, finalHeight[10] = {0};
buildWall(10, 6, op, left, right, height, finalHeight);
for (int i = 0; i < 10; i++) cout << finalHeight[i] << " ";
return 0;
}
#endif // LOCAL
