#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct nd{
int lo,hi;
inline void init(){
lo=0;
hi=2e9;
}
inline nd operator+(nd other){
nd ans={lo,hi};
ans.lo=max(ans.lo,other.lo);
ans.hi=max(ans.hi,other.lo);
ans.hi=min(ans.hi,other.hi);
ans.lo=min(ans.lo,other.hi);
return ans;
}
};
constexpr int maxn=2e6 + 5;
nd tree[4*maxn];
int len=1;
void push(int v){
tree[2*v]=tree[2*v]+tree[v];
tree[2*v+1]=tree[2*v+1]+tree[v];
tree[v].init();
}
void radd(int v,int cs,int ce,int ls,int le,nd x){
if (cs>=ls && ce<=le){
tree[v]=tree[v]+x;
return;
}
if (cs>le || ce<ls) return;
int mid=(cs+ce)/2;
push(v);
radd(2*v,cs,mid,ls,le,x);
radd(2*v+1,mid+1,ce,ls,le,x);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
len=1;
while (len<n) len<<=1;
for (int i=0;i<2*len;i++) tree[i].init();
for (int i=0;i<k;i++){
nd toadd;
if (op[i]==1) toadd={height[i],int(2e9)};
else toadd={0,height[i]};
radd(1,0,len-1,left[i],right[i],toadd);
}
for (int i=1;i<len;i++) push(i);
for (int i=0;i<n;i++){
nd ans=tree[i+len];
cout<<ans.lo<<" "<<ans.hi<<"\n";
finalHeight[i]=min(ans.hi,ans.lo);
}
//for (int i=0;i<n;i++) cout<<finalHeight[i]<<" ";
//cout<<"\n";
}
