#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MX=2000007, INF=1e9+7;
int N;
struct SegTree{
#define mi (le+ri)/2
#define idxl (idx*2+1)
#define idxr (idx*2+2)
struct Node{
int mn, mx, lzmn, lzmx;
Node(){
mx=mn=lzmn=0;
lzmx=INF;
}
}id;
Node combin(Node a, Node b){
Node ret;
ret.mn=min(a.mn, b.mn);
ret.mx=max(a.mx, b.mx);
return ret;
}
Node ST[4*MX];
int letar, ritar, val, ch;
void prop(int idx, int le, int ri){
if(ST[idx].lzmn){
ST[idx].mn=max(ST[idx].lzmn, ST[idx].mn);
ST[idx].mx=max(ST[idx].mn, ST[idx].mx);
if(le<ri){
ST[idxl].lzmn=max(ST[idxl].lzmn, ST[idx].lzmn);
ST[idxl].lzmx=max(ST[idxl].lzmx, ST[idxl].lzmn);
ST[idxr].lzmn=max(ST[idxr].lzmn, ST[idx].lzmn);
ST[idxr].lzmx=max(ST[idxr].lzmx, ST[idxr].lzmn);
}
}
if(ST[idx].lzmx!=INF){
ST[idx].mx=min(ST[idx].lzmx, ST[idx].mx);
ST[idx].mn=min(ST[idx].mx, ST[idx].mn);
if(le<ri){
ST[idxl].lzmx=min(ST[idxl].lzmx, ST[idx].lzmx);
ST[idxl].lzmn=min(ST[idxl].lzmn, ST[idxl].lzmx);
ST[idxr].lzmx=min(ST[idxr].lzmx, ST[idx].lzmx);
ST[idxr].lzmn=min(ST[idxr].lzmn, ST[idxr].lzmx);
}
}
ST[idx].lzmn=0;
ST[idx].lzmx=INF;
}
void upd(int idx, int le, int ri){
prop(idx, le, ri);
if(ri<letar || ritar<le)
return;
if(letar<=le && ri<=ritar){
if(ch&1){
ST[idx].lzmn=max(ST[idx].lzmn, val);
ST[idx].lzmx=max(ST[idx].lzmx, ST[idx].lzmn);
}else{
ST[idx].lzmx=min(ST[idx].lzmx, val);
ST[idx].lzmn=min(ST[idx].lzmn, ST[idx].lzmx);
}
prop(idx, le, ri);
return;
}
upd(idxl, le, mi); upd(idxr, mi+1, ri);
ST[idx]=combin(ST[idxl], ST[idxr]);
}
int que(int idx, int le, int ri){
prop(idx, le, ri);
if(ri<letar || ritar<le)
return 0;
if(letar<=le && ri<=ritar){
return ST[idx].mn;
}
return max(que(idxl, le, mi), que(idxr, mi+1, ri));
}
void update(int op, int le, int ri, int v){
ch=op, letar=le, ritar=ri, val=v;
upd(0, 0, N-1);
}
int query(int x){
letar=ritar=x;
return que(0, 0, N-1);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N=n;
SegTree ST;
for(int i=0, ch, l, r, h; i<k; i++){
ch=op[i], l=left[i], r=right[i], h=height[i];
ST.update(ch, l, r, h);
}
for(int i=0; i<N; i++)
finalHeight[i]=ST.query(i);
return;
}
