#include "wall.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
struct item
{
int mn;
int mx;
};
struct segtree
{
int siz=1;
vector<item>vals;
vector<item>lazy;
void init(int n)
{
while(siz<n)
siz*=2;
vals.resize(4*siz);
}
item mrg(item a,item b)
{
a.mn=min(a.mn,b.mn);
a.mn=max(a.mn,b.mx);
a.mx=max(a.mx,b.mx);
a.mx=min(a.mx,b.mn);
return a;
}
void updaterage(int l,int r,int v,int op,int x,int lx,int rx)
{
if(lx>r||rx<l)return ;
if(lx>=l&&rx<=r)
{
if(op==1)
{
vals[x].mn=max(vals[x].mn,v);
vals[x].mx=max(vals[x].mx,v);
}
else
{
vals[x].mn=min(vals[x].mn,v);
vals[x].mx=min(vals[x].mx,v);
}
return;
}
vals[2*x+1]=mrg(vals[2*x+1],vals[x]);
vals[2*x+2]=mrg(vals[2*x+2],vals[x]);
vals[x].mn=1e9,vals[x].mx=0;
int mid=(lx+rx+1)/2;
updaterage(l,r,v,op,2*x+1,lx,mid-1);
updaterage(l,r,v,op,2*x+2,mid,rx);
}
void updaterage(int l,int r,int v,int op)
{
updaterage(l,r,v,op,0,0,siz-1);
}
int calc(int l,int r,int x,int lx,int rx)
{
vals[2*x+1]=mrg(vals[2*x+1],vals[x]);
vals[2*x+2]=mrg(vals[2*x+2],vals[x]);
if(lx>r||rx<l)return 1e9;
if(lx>=l&&rx<=r)return min(vals[x].mn,vals[x].mx);
int mid=(lx+rx+1)/2;
return min(calc(l,r,2*x+1,lx,mid-1),calc(l,r,2*x+2,mid,rx));
}
int calc(int l,int r)
{
return calc(l,r,0,0,siz-1);
}
};
void buildWall(int n, int k, int x[], int l[], int r[], int h[], int ans[])
{
segtree st;
st.init(n);
for(int i=0; i<k; i++)
{
st.updaterage(l[i],r[i],h[i],x[i]);
}
for(int i=0; i<n; i++)
ans[i]=st.calc(i,i);
}
