#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1 << 17;
int t[N << 2];
int add[N << 2], del[N << 2];
void push(int i, int l, int r){
if(l != r){
add[i << 1] = min(add[i << 1], del[i]);
add[i << 1] = max(add[i << 1], add[i]);
del[i << 1] = min(del[i << 1], del[i]);
del[i << 1] = max(del[i << 1], add[i]);
add[i << 1 | 1] = min(add[i << 1 | 1], del[i]);
add[i << 1 | 1] = max(add[i << 1 | 1], add[i]);
del[i << 1 | 1] = min(del[i << 1 | 1], del[i]);
del[i << 1 | 1] = max(del[i << 1 | 1], add[i]);
}
}
void upd(int l, int r, int i, int from, int to, int val, int type){
push(i, from, to);
if(from > r || to < l) return;
if(from >= l && to <= r){
if(type == 1){
add[i] = max(add[i], val);
del[i] = max(del[i], val);
}
else{
add[i] = min(add[i], val);
del[i] = min(del[i], val);
}
push(i, from, to);
return;
}
add[i] = 0, del[i] = INF;
int mid = (from + to) >> 1;
upd(l, r, i << 1, from, mid, val, type);
upd(l, r, i << 1 | 1, mid + 1, to , val, type);
}
void pushall(int i, int l, int r){
if(l == r) return;
push(i, l, r);
int mid = (l + r) >> 1;
pushall(i << 1, l, mid);
pushall(i << 1 | 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
memset(del, INF, sizeof del);
for(int i = 0; i < k; i++){
upd(l[i], r[i], 1, 0, N - 1, h[i], op[i]);
}
pushall(1, 0, N - 1);
for(int i = 0; i < n; i++){
ans[i] = add[i + N];
}
}
