#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+4;
const int inf = 1e9;
int n,k;
int tp[N],levo[N],desno[N],vis[N];
struct sta{
int mx,mn; /// maximise from below, minimise from above
} drvo[4*N],lazy[4*N];
sta spojimx(sta a,int maks){
if(a.mx <= a.mn){
if(maks <= a.mx) return a;
else if(maks > a.mx && maks <= a.mn) return {maks,a.mn};
else return {maks,maks};
}
else{
if(maks <= a.mn) return a;
else return {maks,maks};
}
}
sta spojimn(sta a,int mini){
return {a.mx,min(a.mn,mini)};
}
sta spoji(sta a,sta b){
return spojimn(spojimx(a,b.mx),b.mn);
}
void push(int i,int j,int node){
if(lazy[node].mx != 0 || lazy[node].mn != inf){
//cout << "radim " << i << " " << j << " " << node << " " << lazy[node].mx << " " << lazy[node].mn << endl;
if(i == j){
//cout << "spajam " << drvo[node].mx << " " << drvo[node].mn << " sa " << lazy[node].mx << " " << lazy[node].mn << " dobijam ";
drvo[node] = spoji(drvo[node],lazy[node]);
//cout << drvo[node].mx << " " << drvo[node].mn << endl;
}
if(i != j){
//cout << "ostalo od pre " << lazy[2*node].mx << " " << lazy[2*node].mn << endl;
lazy[2*node] = spoji(lazy[2*node],lazy[node]);
/*cout << "postaje " << lazy[2*node].mx << " " << lazy[2*node].mn << endl;
cout << "ostalo od pre " << lazy[2*node+1].mx << " " << lazy[2*node+1].mn << endl;*/
lazy[2*node+1] = spoji(lazy[2*node+1],lazy[node]);
//cout << "postaje " << lazy[2*node+1].mx << " " << lazy[2*node+1].mn << endl;
}
lazy[node] = {0,inf};
}
}
void update(int i,int j,int l,int r,sta val,int node){
push(i,j,node);
if(j < l || i > r) return;
if(l <= i && r >= j){
lazy[node] = val;
push(i,j,node);
return;
}
int mid = i+(j-i)/2;
update(i,mid,l,r,val,2*node);
update(mid+1,j,l,r,val,2*node+1);
}
sta daj(int pos){
int i = 1,j = n,node = 1;
while(i != j){
push(i,j,node);
int mid = i+(j-i)/2;
if(pos <= mid){
node *= 2;
j = mid;
}
else{
node *= 2;
node++;
i = mid+1;
}
}
push(i,j,node);
return drvo[node];
}
void buildWall(int br1,int br2,int op[],int left[],int right[],int height[],int finalHeight[]){
n = br1;
k = br2;
for(int i = 0; i < k; i++){
tp[i+1] = op[i];
levo[i+1] = left[i]+1;
desno[i+1] = right[i]+1;
vis[i+1] = height[i];
}
for(int i = 0; i <= 4*n; i++){
drvo[i] = {0,inf};
lazy[i] = {0,inf};
}
for(int i = 1; i <= k; i++){
if(tp[i] == 1){ /// maximise from below
update(1,n,levo[i],desno[i],{vis[i],inf},1);
}
else{ /// minimise from above
update(1,n,levo[i],desno[i],{0,vis[i]},1);
}
/*vector <pair<int,int>> h;
for(int j = 1; j <= n; j++){
sta x = daj(j);
h.push_back({x.mx,x.mn});
}
for(auto f : h) cout << f.first << " " << f.second << " ";
cout << endl << endl;*/
}
for(int i = 1; i <= n; i++){
sta x = daj(i);
finalHeight[i-1] = min(x.mn,x.mx);
}
}
