#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define UP1(i, n) for (int i = 0; i < (n); i++)
#define UP2(i, a, b) for (int i = (a); i <= (b); i++)
#define UP3(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define DN1(i, n) for (int i = (n) - 1; i >= 0; i--)
#define DN2(i, a, b) for (int i = (a); i >= (b); i--)
#define DN3(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
#define FOR_IMPL(_1, _2, _3, _4, NAME, ...) NAME
#define FOR_UP(...) FOR_IMPL(__VA_ARGS__, UP3, UP2, UP1) (__VA_ARGS__)
#define FOR_DN(...) FOR_IMPL(__VA_ARGS__, DN3, DN2, DN1) (__VA_ARGS__)
#define POPCOUNT(n) __builtin_popcountll(n)
#define CLZ(n) __builtin_clzll(n)
#define CTZ(n) __builtin_ctzll(n)
#define LOG(n) __lg(n)
#define BIT(n, i) (((n) >> (i)) & 1LL)
#define FLIP(n, i) ((n) ^ (1LL << (i)))
#define ON(n, i) ((n) | (1LL << (i)))
#define OFF(n, i) ((n) & ~(1LL << (i)))
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
#if __cplusplus <= 201402L
template <typename T> T gcd(T a, T b) {
return __gcd(a, b);
}
template <typename T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
return uniform_int_distribution<long long>(l, r)(rng);
}
template <class T> void remove_duplicate(vector<T> &v) {
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
}
template <class T> bool maximize(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <class T> bool minimize(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
const int N = 2e6 + 24;
const int INF = 1e9;
int n, q;
struct Node {
int L = 0, R = INF;
} t[2 * N];
void push(int id) {
// if (id >= n) return;
FOR_UP (child, 2 * id, 2 * id + 1) {
if (child >= 2 * n) continue;
maximize(t[child].L, t[id].L);
maximize(t[child].R, t[id].L);
minimize(t[child].R, t[id].R);
minimize(t[child].L, t[id].R);
}
t[id] = Node();
}
void push_down(int i) {
FOR_DN (j, LOG(i), 1) {
int id = (i >> j);
push(id);
}
}
void chmin(int l, int r, int x) {
l += n; r += n + 1;
push_down(l); push_down(r - 1);
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
minimize(t[l].R, x);
minimize(t[l].L, x);
l++;
}
if (r & 1) {
r--;
minimize(t[r].R, x);
minimize(t[r].L, x);
}
}
}
void chmax(int l, int r, int x) {
l += n; r += n + 1;
push_down(l); push_down(r - 1);
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
maximize(t[l].L, x);
maximize(t[l].R, x);
l++;
}
if (r & 1) {
r--;
maximize(t[r].L, x);
maximize(t[r].R, x);
}
}
}
int get(int i) {
i += n;
push_down(i);
return t[i].L;
}
void buildWall(int n_, int q_, int op[], int left[], int right[], int height[], int finalHeight[]) {
n = n_, q = q_;
FOR_UP (i, q) {
if (op[i] == 1) {
chmax(left[i], right[i], height[i]);
}
else {
chmin(left[i], right[i], height[i]);
}
}
FOR_UP (i, n) {
finalHeight[i] = get(i);
}
}
