// Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "wall.h"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
struct node {
int lo, hi;
node() {
lo = 0;
hi = 1e5;
}
};
const int maxn = 2e6 + 5;
node st[4 * maxn];
int n;
void change(int p, int op, int v) {
if (op == 1)
st[p].lo = max(st[p].lo, v), st[p].hi = max(st[p].hi, v);
else
st[p].lo = min(st[p].lo, v), st[p].hi = min(st[p].hi, v);
}
void update(int i, int j, int op, int v, int p = 1, int L = 0, int R = n - 1) {
if (i > R || j < L) return;
if (i <= L && R <= j) {
change(p, op, v);
return;
}
change(2 * p, 1, st[p].lo);
change(2 * p + 1, 1, st[p].lo);
change(2 * p, 2, st[p].hi);
change(2 * p + 1, 2, st[p].hi);
st[p].lo = 0, st[p].hi = 1e5;
int M = (L + R) / 2;
update(i, j, op, v, 2 * p, L, M);
update(i, j, op, v, 2 * p + 1, M + 1, R);
}
int *arr;
void prop(int p = 1, int L = 0, int R = n - 1) {
if (L == R) {
arr[L] = st[p].lo;
return;
}
change(2 * p, 1, st[p].lo);
change(2 * p + 1, 1, st[p].lo);
change(2 * p, 2, st[p].hi);
change(2 * p + 1, 2, st[p].hi);
int M = (L + R) / 2;
prop(2 * p, L, M);
prop(2 * p + 1, M + 1, R);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
n = N;
arr = finalHeight;
for (int i = 0; i < k; i++) update(left[i], right[i], op[i], height[i]);
prop();
}
