#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int L = (1<<21), inf = 1e9;
struct SEG {
int mn[2*L], mx[2*L];
void init () {
for(int i=2*L;i--;) {
mn[i] = 0;
mx[i] = inf;
}
}
void relax (int P, int O, int V) {
if(O == 1) {
mn[P] = max(mn[P], V);
if(mn[P] > mx[P]) mx[P] = mn[P];
}
else {
mx[P] = min(mx[P], V);
if(mn[P] > mx[P]) mn[P] = mx[P];
}
}
void lazydown (int P) {
relax(2*P, 1, mn[P]);
relax(2*P, 2, mx[P]);
relax(2*P+1, 1, mn[P]);
relax(2*P+1, 2, mx[P]);
mn[P] = 0;
mx[P] = inf;
}
void upd (int S, int E, int O, int V, int SS = 0, int SE = L-1, int P = 1) {
if(S <= SS && SE <= E) {
relax(P, O, V);
return;
}
if(E < SS || SE < S) return;
lazydown(P);
int M = (SS+SE)/2;
upd(S, E, O, V, SS, M, 2*P);
upd(S, E, O, V, M+1, SE, 2*P+1);
}
int get (int I, int SS = 0, int SE = L-1, int P = 1) {
if(SS == SE) return mn[P];
lazydown(P);
int M = (SS+SE)/2;
return I <= M ? get(I, SS, M, 2*P) : get(I, M+1, SE, 2*P+1);
}
} seg;
void buildWall (int N, int K, int O[], int L[], int R[], int H[], int FH[]){
seg.init();
for(int i=0;i<K;i++) {
seg.upd(L[i], R[i], O[i], H[i]);
}
for(int i=0;i<N;i++) {
FH[i] = seg.get(i);
}
}
