#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define gg exit(0);
#include "wall.h"
const int INF=1e9,
N=2000010;
int add[N*4],rev[N*4];
void Add(int &i,int &j,int t){
if(j<=t){
i=j=t;
//i=t;
//j=INF;
} else{
i=max(i,t);
}
}
void Rev(int &i,int &j,int t){
j=min(j,t);
}
void join(int i,int j){
Add(add[i],rev[i],add[j]);
Rev(add[i],rev[i],rev[j]);
}
void upd(int s,int l,int r,int u,int v,int op,int h){
if(l>v||u>r) return;
if(u<=l&&r<=v){
if(op==1){
Add(add[s],rev[s],h);
} else{
Rev(add[s],rev[s],h);
}
return;
}
join(2*s,s); join(2*s+1,s);
add[s]=-INF;
rev[s]=INF;
int m=(l+r)/2;
upd(2*s,l,m,u,v,op,h); upd(2*s+1,m+1,r,u,v,op,h);
}
void build(int s,int l,int r){
add[s]=0; rev[s]=INF;
if(l==r){
return;
}
int m=(l+r)/2;
build(2*s,l,m); build(2*s+1,m+1,r);
}
void get(int s,int l,int r,int ans[]){
if(l==r){
ans[l]=min(add[s],rev[s]);
return;
}
int m=(l+r)/2;
join(2*s,s); join(2*s+1,s);
get(2*s,l,m,ans); get(2*s+1,m+1,r,ans);
}
void buildWall(int n,int k,int op[],int l[],int r[],int h[],int ans[]){
forinc(i,0,k-1){
upd(1,0,n-1,l[i],r[i],op[i],h[i]);
}
/**
//cerr<<add[1]<<" "<<rev[1];
//cout<<add[3]<<" "<<rev[3];
join(3,1);
//Add(add[3],rev[3],1);
//+ -INF -1
+2 -INF
+1 -INF
+6 -4 +4
+2 -4 + 4
>= - INF <=1 +1
= 1
//cout<<add[3]<<" "<<rev[3];
//gg
//join(6,3);
//cout<<add[6]<<" "<<rev[6];
gg
join(1,3);
gg
*/
get(1,0,n-1,ans);
}
