#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2e6 + 5;
int n;
struct SegTree{
int mn[N * 4], mx[N * 4];
SegTree(){
memset(mn, -1, sizeof(mn));
memset(mx, -1, sizeof(mx));
}
void push(int v){
if(mn[v] != -1){
if(v * 2 < N * 4){
if(mn[v * 2] == -1) mn[v * 2] = mn[v];
else mn[v * 2] = max(mn[v * 2], mn[v]);
if(mx[v * 2] != -1) mx[v * 2] = max(mx[v * 2], mn[v]);
if(mn[v * 2 + 1] == -1) mn[v * 2 + 1] = mn[v];
else mn[v * 2 + 1] = max(mn[v * 2 + 1], mn[v]);
if(mx[v * 2 + 1] != -1) mx[v * 2 + 1] = max(mx[v * 2 + 1], mn[v]);
}
mn[v] = -1;
}
if(mx[v] != -1){
if(v * 2 < N * 4){
if(mx[v * 2] == -1) mx[v * 2] = mx[v];
else mx[v * 2] = min(mx[v * 2], mx[v]);
if(mn[v * 2] != -1) mn[v * 2] = min(mn[v * 2], mx[v]);
if(mx[v * 2 + 1] == -1) mx[v * 2 + 1] = mx[v];
else mx[v * 2 + 1] = min(mx[v * 2 + 1], mx[v]);
if(mn[v * 2 + 1] != -1) mn[v * 2 + 1] = min(mn[v * 2 + 1], mx[v]);
}
mx[v] = -1;
}
}
void updatemin(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1){
if(l > r) return;
else if(l == tl && r == tr){
if(mn[v] == -1) mn[v] = val;
else{
mn[v] = max(mn[v], val);
}
if(mx[v] != -1) mx[v] = max(mx[v], val);
}
else{
push(v);
int tm = tl + (tr - tl) / 2;
updatemin(l, min(tm, r), val, v * 2, tl, tm);
updatemin(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
}
}
void updatemax(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1){
if(l > r) return;
else if(l == tl && r == tr){
if(mx[v] == -1) mx[v] = val;
else{
mx[v] = min(mx[v], val);
}
if(mn[v] != -1) mn[v] = min(mn[v], val);
}
else{
push(v);
int tm = tl + (tr - tl) / 2;
updatemax(l, min(tm, r), val, v * 2, tl, tm);
updatemax(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
}
}
void findarr(int *arr, int v = 1, int l = 0, int r = n - 1){
if(l == r) arr[l] = max(mn[v], 0);
else{
push(v);
int m = l + (r - l) / 2;
findarr(arr, v * 2, l, m);
findarr(arr, v * 2 + 1, m + 1, r);
}
}
};
SegTree sgt;
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
for(int i = 0; i < k; i++){
if(op[i] == 1) sgt.updatemin(left[i], right[i], height[i]);
else if(op[i] == 2) sgt.updatemax(left[i], right[i], height[i]);
}
sgt.findarr(finalHeight);
}
