#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
#define ll long long
#define debug(x) cerr << #x << ' ' << x << '\n'
#define dbg(x) cerr<<#x<<' '<<x<<' '
const int base=31;
const int MOD=1e9+7;
const int N=1e6+5;
const int INF=1e9;
const int mx=2e6;
struct segtree{
int max1,max2,min1,min2;
} st[mx*4+5];
int n,m,k;
array<int,4>queries[N];
void pushMin(int id,int val)
{
if (st[id].min1>=val)
{
st[id]={val,-INF,val,INF};
}
else if (val<st[id].max1)
{
if (st[id].min2==st[id].max1) st[id].min2=val;
st[id].max1=val;
}
}
void pushMax(int id,int val)
{
if (st[id].max1<=val)
{
st[id]={val,-INF,val,INF};
}
else if (st[id].min1<val)
{
if (st[id].max2==st[id].min1) st[id].max2=val;
st[id].min1=val;
}
}
void up(int id)
{
st[id].max1=max(st[id<<1].max1,st[id<<1|1].max1);
st[id].max2=max(st[id<<1].max2,st[id<<1|1].max2);
st[id].min1=min(st[id<<1].min1,st[id<<1|1].min1);
st[id].min2=min(st[id<<1].min2,st[id<<1|1].min2);
if (st[id<<1].max1!=st[id].max1) st[id].max2=max(st[id].max2,st[id<<1].max1);
if (st[id<<1|1].max1!=st[id].max1) st[id].max2=max(st[id].max2,st[id<<1|1].max1);
if (st[id<<1].min1!=st[id].min1) st[id].min2=min(st[id].min2,st[id<<1].min1);
if (st[id<<1|1].min1!=st[id].min1) st[id].min2=min(st[id].min2,st[id<<1|1].min1);
}
void down(int id)
{
pushMin(id<<1,st[id].max1);
pushMin(id<<1|1,st[id].max1);
pushMax(id<<1,st[id].min1);
pushMax(id<<1|1,st[id].min1);
}
void updateMax(int id,int l,int r,int u,int v,int x)
{
if (v<l||r<u||x<=st[id].min1) return;
if (u<=l&&r<=v&&x<st[id].min2)
{
pushMax(id,x);
return;
}
int mid=l+r>>1;
down(id);
updateMax(id<<1,l,mid,u,v,x);
updateMax(id<<1|1,mid+1,r,u,v,x);
up(id);
}
void updateMin(int id,int l,int r,int u,int v,int x)
{
if (v<l||r<u||x>=st[id].max1) return;
if (u<=l&&r<=v&&st[id].max2<x)
{
pushMin(id,x);
return;
}
int mid=l+r>>1;
down(id);
updateMin(id<<1,l,mid,u,v,x);
updateMin(id<<1|1,mid+1,r,u,v,x);
up(id);
}
int get(int id,int l,int r,int x)
{
if (l==r) return st[id].max1;
int mid=l+r>>1;
down(id);
if (x<=mid) return get(id<<1,l,mid,x);
return get(id<<1|1,mid+1,r,x);
}
void build(int id,int l,int r)
{
if (l==r)
{
st[id]={0,-INF,0,INF};
return;
}
int mid=l+r>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
up(id);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
build(1,0,n-1);
for (int i=0;i<k;i++)
{
if (op[i]==1)
{
updateMax(1,0,n-1,left[i],right[i],height[i]);
} else updateMin(1,0,n-1,left[i],right[i],height[i]);
}
for (int i=0;i<n;i++)
{
finalHeight[i]=get(1,0,n-1,i);
}
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
