///~~~LOTA~~~///
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define LIMIT 50000001
#define MAXN 100000
int L[4*MAXN];
int R[4*MAXN];
int ANS[MAXN];
void get(int l=0,int r=MAXN,int v=1,int s=0,int e=MAXN){
l=max(l,L[v]);
r=min(r,R[v]);
if(e-s==1){
ANS[s]=min(l,r);
return;
}
int lc,rc,mid;
lc=2*v;
rc=2*v+1;
mid=(s+e)/2;
get(l,r,lc,s,mid);
get(l,r,rc,mid,e);
}
void update(int l,int r,int x,int i,int v=1,int s=0,int e=MAXN){
if(r<=s || e<=l || s>=e) return;
if(l<=s && e<=r){
if(i==1) L[v]=max(L[v],x);
else R[v]=min(R[v],x);
return;
}
int lc,rc,mid;
lc=2*v;
rc=2*v+1;
mid=(s+e)/2;
update(l,r,x,i,lc,s,mid);
update(l,r,x,i,rc,mid,e);
}
void buildWall(int n,int m,int t[],int l[],int r[],int h[],int ans[]){
for(int i=0;i<4*MAXN;i++)
R[i]=MAXN;
for(int i=0;i<m;i++){
if(n*m<LIMIT){
for(int j=l[i];j<=r[i];j++){
if(t[i]==1) ANS[j]=max(ANS[j],h[i]);
else ANS[j]=min(ANS[j],h[i]);
}
}
else update(l[i],r[i]+1,h[i],t[i]);
}
if(n*m>=LIMIT) get();
for(int i=0;i<n;i++) ans[i]=ANS[i];
}
