#include "wall.h"
#include<bits/stdc++.h>
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second
using namespace std;
pair<int, int> seg[8000010];
void update(int id, int L, int R, int l, int r, int cur, bool op) {
cur = max(cur, seg[id].F); cur = min(cur, seg[id].S);
if (L > r || l > R) return;
if (L >= l && r >= R) {if (!op) seg[id].F = cur; else seg[id].S = cur; return ;}
int M = (L + R) / 2, x = 2 * id, y = x + 1;
update(x, L, M, l, r, cur, op);
update(y, M + 1, R, l, r, cur, op);
}
void make(int id, int L, int R, int cur, int *ans){
cur = max(cur, seg[id].F); cur = min(cur, seg[id].S);
if (L == R) {ans[L] = cur; return ;}
int M = (L + R) / 2, x = 2 * id, y = x + 1;
make(x, L, M, cur, ans);
make(y, M + 1, R, cur, ans);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
for (int i = 1; i <= 4 * n; i++) seg[i] = {0, INT_MAX};
for (int i = k - 1; i >= 0; i--) update(l[i], r[i], 1, 0, n - 1, h[i], op[i] - 1);
make(0, n - 1, 1, 0, ans);
return ;
}
