#include "wall.h"
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=2e6+5, Log=21, pot=(1<<Log);
int prop[pot*2][4];
void precompute(){
for(int i=1; i<pot*2; i++){
prop[i][1]=-1;
prop[i][3]=-1;
}
}
void dodaj(int x, int a, int b){
if(prop[x][1]==-1){
prop[x][0]=a;
prop[x][1]=b;
}
else if(prop[x][3]==-1){
if(b==prop[x][1]){
if(b){
prop[x][0]=max(prop[x][0], a);
}
else{
prop[x][0]=min(prop[x][0], a);
}
}
else{
prop[x][2]=a;
prop[x][3]=b;
}
}
else{
if(prop[x][3]==b){
if(b){
prop[x][2]=max(prop[x][2], a);
}
else{
prop[x][2]=min(prop[x][2], a);
}
}
else{
if(b){
if(a<=prop[x][2] && prop[x][0]<=prop[x][2]){
prop[x][0]=max(prop[x][0], a);
}
else if(a>prop[x][2]){
prop[x][0]=prop[x][2];
prop[x][1]=prop[x][3];
prop[x][2]=a;
prop[x][3]=b;
}
}
else{
if(a>=prop[x][2] && prop[x][0]>=prop[x][2]){
prop[x][0]=min(prop[x][0], a);
}
else if(a<prop[x][2]){
prop[x][0]=prop[x][2];
prop[x][1]=prop[x][3];
prop[x][2]=a;
prop[x][3]=b;
}
}
}
}
}
void propagate(int x){
if(prop[x][1]==-1){
return;
}
dodaj(x*2, prop[x][0], prop[x][1]);
dodaj(x*2+1, prop[x][0], prop[x][1]);
prop[x][1]=-1;
if(prop[x][3]!=-1){
dodaj(x*2, prop[x][2], prop[x][3]);
dodaj(x*2+1, prop[x][2], prop[x][3]);
prop[x][3]=-1;
}
}
void update(int x, int L, int D, int l, int d, int a, int b){
if(L>=l && D<=d){
dodaj(x, a, b);
return;
}
propagate(x);
if((L+D)/2>=l){
update(x*2, L, (L+D)/2, l, d, a, b);
}
if((L+D)/2+1<=d){
update(x*2+1, (L+D)/2+1, D, l, d, a, b);
}
}
void kraj(int x){
if(x>=pot){
return;
}
propagate(x);
kraj(x*2);
kraj(x*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
precompute();
for(int i=0; i<k; i++){
if(op[i]==2){
op[i]=0;
}
update(1, 0, pot-1, left[i], right[i], height[i], op[i]);
}
kraj(1);
int x;
for(int i=0; i<n; i++){
x=pot+i;
if(prop[x][3]!=-1){
if(prop[x][3]){
finalHeight[i]=prop[x][2];
}
else{
finalHeight[i]=min(prop[x][0], prop[x][2]);
}
}
else if(prop[x][1]==1){
finalHeight[i]=prop[x][0];
}
}
}
