#include "wall.h"
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
const int inf = 0x3f3f3f3f;
struct segTree{
int l, r;
segTree *tl, *tr;
int mx1, mx2, mxl, mn1, mn2, mnl;
segTree(int a, int b){
l = a, r = b;
mx1 = mn1 = 0, mx2 = -inf, mn2 = inf, mxl = mnl = -1;
if(l != r){
int mid = (l + r) / 2;
tl = new segTree(l, mid);
tr = new segTree(mid + 1, r);
}
}
void upx(int x){
if(mx1 == mn1) mx1 = x;
if(mx2 == mn1) mx2 = x;
mn1 = x, mnl = x;
}
void upn(int x){
if(mn1 == mx1) mn1 = x;
if(mn2 == mx1) mn2 = x;
mx1 = x, mnl = x;
}
void pull(){
mx1 = max(tl->mx1, tr->mx1);
mx2 = max(tl->mx2, tr->mx2);
if(tl->mx1 != mx1) mx2 = max(mx2, tl->mx1);
if(tr->mx1 != mx1) mx2 = max(mx2, tr->mx1);
mn1 = min(tl->mn1, tl->mn1);
mn2 = min(tl->mn2, tr->mn2);
if(tl->mn1 != mn1) mn2 = min(mn2, tl->mn2);
if(tr->mn1 != mn1) mn2 = min(mn2, tr->mn2);
}
void push(){
if(~mxl) tl->upx(mxl), tr->upx(mxl);
if(~mnl) tl->upn(mnl), tr->upn(mnl);
mxl = mnl = -1;
}
void adx(int a, int b, int v){
if(b < l || r < a || v <= mn1) return;
if(a <= l && r <= b && v < mn2) return upx(v);
tl->push(), tr->push();
tl->adx(a, b, v), tr->adx(a, b, v);
pull();
}
void adn(int a, int b, int v){
if(b < l || r < a || v >= mx1) return;
if(a <= l && r <= b && v > mx2) return upn(v);
tl->push(), tr->push();
tl->adx(a, b, v), tr->adx(a, b, v);
pull();
}
void sol(int ans[]){
if(l == r) return (void)(ans[l] = mn1);
tl->push(), tr->push();
tl->sol(ans), tr->sol(ans);
}
};
void buildWall(int n, int k, int a[], int l[], int r[], int h[], int ans[]){
segTree tre(0, n - 1);
for(int i = 0; i < k; i++){
if(a[i] & 1) tre.adx(l[i], r[i], h[i]);
else tre.adn(l[i], r[i], h[i]);
}
tre.sol(ans);
}
