#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int f[8000005];
int f1[8000005];
int res[2000005];
void push(int id){
if (f[id]!=f1[id]){
return;
}
f[id*2]=f1[id*2]=f[id];
f[id*2+1]=f1[id*2+1]=f[id];
}
void update(int id,int l,int r,int x,int y,int val){
if (val<=f[id] || x>r || y<l){
return;
}
if (l>=x && y>=r && val>f1[id]){
f[id]=f1[id]=val;
return;
}
int mid=(l+r)/2;
push(id);
update(id*2,l,mid,x,y,val);
update(id*2+1,mid+1,r,x,y,val);
f[id]=min(f[id*2],f[id*2+1]);
f1[id]=max(f1[id*2],f1[id*2+1]);
}
void update1(int id,int l,int r,int x,int y,int val){
if (val>=f1[id] || x>r || y<l){
return;
}
if (l>=x && y>=r && val<f[id]){
f[id]=f1[id]=val;
return;
}
int mid=(l+r)/2;
push(id);
update1(id*2,l,mid,x,y,val);
update1(id*2+1,mid+1,r,x,y,val);
f[id]=min(f[id*2],f[id*2+1]);
f1[id]=max(f1[id*2],f1[id*2+1]);
}
void bruh(int id,int l,int r){
if (l==r){
res[l]=f[id];
// cerr << res[l] << " ";
return;
}
int mid=(l+r)/2;
push(id);
bruh(id*2,l,mid);
bruh(id*2+1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=0;i<k;i++){
if (op[i]==1){
update(1,0,n-1,left[i],right[i],height[i]);
}else{
update1(1,0,n-1,left[i],right[i],height[i]);
}
// cerr << "\n";
}
bruh(1,0,n-1);
for (int i=0;i<n;i++){
finalHeight[i]=res[i];
}
return;
}
