#include "wall.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define ll long long
using namespace std;
const char en='\n';
const int MOD=1000000007;
#pragma GCC optimize("O2,unroll-loops")
const int N=100010,M=1<<17;
int ee,prop[M*2+10];
pii qu1[M*2+10][5],qu2[M*2+10][5];
int h[N];
inline void maa(int&a,const int&b)
{
if (b>a) a=b;
}
inline void mii(int&a,const int&b)
{
if (b<a) a=b;
}
void pus(pii a[],pii x)
{
int z=4;
while (z && a[z].x==0) --z;
if (z==4)
{
a[0]={0,0};
for (int i=0;i<4;++i) a[i]=a[i+1];
a[4]=x;
}
else a[z+1]=x;
}
void pro1(int i)
{
++ee;
if (i<M)
{
maa(prop[i*2],prop[i]);
maa(prop[i*2+1],prop[i]);
prop[i]=0;
int z=4;
while (z>=0 && qu1[i][z].x==0) --z;
while (z>=0)
{
pus(qu1[i*2],qu1[i][z]);
pus(qu1[i*2+1],qu1[i][z]);
qu1[i][z]={0,0};
--z;
}
}
}
void upd1(int&l,int&r,int&x,int&o,int lo=0,int hi=M,int i=1)
{
pus(qu1[i],{o,x});
pro1(i);
if (lo>=l && hi<=r)
{
prop[i]=max(prop[i],x);
//pro1(i);
return;
}
if (lo>=r || hi<=l) return;
int mid=(lo+hi)/2;
upd1(l,r,x,o,lo,mid,i*2);
upd1(l,r,x,o,mid,hi,i*2+1);
}
void pro2(int i)
{
++ee;
if (i<M)
{
mii(prop[i*2],prop[i]);
mii(prop[i*2+1],prop[i]);
prop[i]=MOD;
int z=4;
while (z>=0 && qu2[i][z].x==0) --z;
while (z>=0)
{
pus(qu2[i*2],qu2[i][z]);
pus(qu2[i*2+1],qu2[i][z]);
qu2[i][z]={0,0};
--z;
}
}
}
void upd2(int&l,int&r,int&x,int&o,int lo=0,int hi=M,int i=1)
{
pus(qu2[i],{o,x});
pro2(i);
if (lo>=l && hi<=r)
{
prop[i]=min(prop[i],x);
//pro2(i);
return;
}
if (lo>=r || hi<=l) return;
int mid=(lo+hi)/2;
upd2(l,r,x,o,lo,mid,i*2);
upd2(l,r,x,o,mid,hi,i*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
assert(n<=1e5);
vector<int> res(n);
if (n*1ll*k<=5e8)
{
int z=0;
for (int o=0;o<k;++o)
{
assert(left[o]>=0 && left[o]<n);
assert(right[o]>=left[o] && right[o]<n);
assert(right[o]-left[o]<n);
if (op[o]==1)
{
for (int i=left[o];i<=right[o];++i) maa(res[i],height[o]);
}
else
{
for (int i=left[o];i<=right[o];++i) mii(res[i],height[o]);
}
}
for (int i=0;i<n;++i) finalHeight[i]=res[i];
return;
}
int o=0;
for (;o<k && op[o]==1;++o)
{
int x=left[o],y=right[o]+1,z=height[o],w=o+1;
upd1(x,y,z,w);
}
for (int i=1;i<M;++i) pro1(i);
for (int i=1;i<M;++i) prop[i]=MOD;
for (;o<k && op[o]!=1;++o)
{
int x=left[o],y=right[o]+1,z=height[o],w=o+1;
upd2(x,y,z,w);
}
for (int i=1;i<M;++i) pro2(i);
for (int i=M;i<M+n;++i) finalHeight[i-M]=prop[i];
}
