#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define FOR(i, a, b) for(ll i = (a); i < (b); i++)
#define FORD(i, a, b) for(ll i = (a); i >= (b); i--)
const int inf = 2e9;
const int N = 2e6 + 5;
vector<int> mn(N * 4, 0);
vector<int> mx(N * 4, inf);
void update(int v, int tl, int tr, int l, int r, int cur, int state) {
cur = max(cur, mn[v]);
cur = min(cur, mx[v]);
if(l > tr || r < tl) return;
if(l <= tl && r >= tr) {
if(state == 1) mn[v] = cur;
if(state == 2) mx[v] = cur;
return;
}
ll tm = (tl + tr) / 2;
update(v * 2, tl, tm, l, r, cur, state);
update(v * 2 + 1, tm + 1, tr, l, r, cur, state);
}
void answer(int v, int tl, int tr, int cur, int finalHeight[]) {
cur = max(cur, mn[v]);
cur = min(cur, mx[v]);
if(tl == tr) {
finalHeight[tl] = cur;
return;
}
ll tm = (tl + tr) / 2;
answer(v * 2, tl, tm, cur, finalHeight);
answer(v * 2 + 1, tm + 1, tr, cur, finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
FORD(i, k - 1, 0) {
update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
}
answer(1, 0, n - 1, 0, finalHeight);
}
