#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const long maxn=2e6+5;
int tree[maxn*4], mint[maxn*4], maxt[maxn*4], push[maxn*4], a[maxn];
void get(int v, int l, int r, int tl, int tr, int h, int op){
if(push[v]!=-1){
mint[v]=maxt[v]=push[v];
if(tl!=tr){
push[v*2]=push[v*2+1]=push[v];
}
push[v]=-1;
}
if(tl>r||l>tr){
return;
}
if(tl>=l&&tr<=r){
if(op==1&&maxt[v]<h||op==2&&mint[v]>h){
mint[v]=maxt[v]=h;
if(tl!=tr){
push[v*2]=push[v*2+1]=h;
}
return;
}else if(op==1&&mint[v]>=h||op==2&&maxt[v]<=h){
return;
}
}
int tm=(tl+tr)/2;
get(v*2, l, r, tl, tm, h, op);
get(v*2+1, l, r, tm+1, tr, h, op);
mint[v]=min(mint[v*2], mint[v*2+1]);
maxt[v]=max(maxt[v*2], maxt[v*2+1]);
}
void bt(int v, int tl, int tr){
if(tl==tr){
a[tl]=mint[v];
return;
}
int tm=(tl+tr)/2;
bt(v*2, tl, tm);
bt(v*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0; i<k; i++){
get(1, left[i], right[i], 0, n-1, height[i], op[i]);
}
bt(1, 0, n-1);
for(int i=0; i<n; i++){
finalHeight[i]=a[i];
}
return;
}
/*int main(){
int n, k;
cin >> n >> k;
int op[k], left[k], right[k], height[k], finalHeight[k]{};
for(int i=0; i<k; i++){
cin >> op[i] >> left[i] >> right[i] >> height[i];
}
buildWall(n, k, op, left, right, height, finalHeight);
for(int i=0; i<n; i++){
cout << finalHeight[i] << " ";
}
return 0;
}*/
