#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 2000001;
int l[nmax * 4], r[nmax * 4];
void upd(int a, int b){
if(l[a] > r[b])
l[b] = r[b] = l[a];
else{
if(r[a] < l[b])
l[b] = r[b] = r[a];
else{
l[b] = max(l[a], l[b]);
r[b] = min(r[a], r[b]);
}
}
}
void push(int v){
upd(v, 2 * v);
upd(v, 2 * v + 1);
}
void update(int v, int L, int R, int st, int fin, int val, int op){
if(L > fin || R < st)
return;
if(L >= st && R <= fin){
if(op == 1){
l[v] = max(l[v], val);
r[v] = max(r[v], l[v]);
}
else{
r[v] = min(r[v], val);
l[v] = min(r[v], l[v]);
}
return;
}
int m = (L + R) / 2;
push(v);
update(2 * v, L, m, st, fin, val, op);
update(2 * v + 1, m + 1, R, st, fin, val, op);
l[v] = min(l[2 * v], l[2 * v + 1]);
r[v] = max(r[2 * v], r[2 * v + 1]);
}
int ans[nmax];
void get(int v, int L, int R){
if(L == R){
ans[L] = l[v];
return;
}
int M = (L + R) / 2;
push(v);
get(2 * v, L, M);
get(2 * v + 1, M + 1, R);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; i++){
update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
}
get(1, 0, n - 1);
for(int i = 0; i < n; i++)
finalHeight[i] = ans[i];
return;
}
