#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>lazy[8000001];
vector<int>v;
void smeni(int i,int k1)
{
for(int j=0;j<lazy[i].size();j++)
{
if(lazy[i][j].first==1)v[k1]=max(v[k1],lazy[i][j].second);
else v[k1]=min(v[k1],lazy[i][j].second);
}
}
void add(int i,int i1)
{
for(int j=0;j<lazy[i].size();j++)
{
auto p=lazy[i][j];
if(lazy[i1].size()==0)lazy[i1].push_back(p);
else if(lazy[i1].size()==1)
{
if(lazy[i1][0].first!=p.first)lazy[i1].push_back(p);
else if(lazy[i1][0].first==1)lazy[i1][0].second=max(lazy[i1][0].second,p.second);
else lazy[i1][0].second=min(lazy[i1][0].second,p.second);
}
else
{
if(lazy[i1][1].first==p.first)
{
if(lazy[i1][1].first==1)lazy[i1][1].second=max(lazy[i1][1].second,p.second);
else lazy[i1][1].second=min(lazy[i1][1].second,p.second);
}
else
{
if(lazy[i1][0].second>p.second&&p.first==2)
{
lazy[i1][0].second=p.second;
swap(lazy[i1][0],lazy[i1][1]);
}
else if(lazy[i1][0].second<p.second&&p.first==1)
{
lazy[i1][0].second=p.second;
swap(lazy[i1][0],lazy[i1][1]);
}
}
}
if(lazy[i1].size()==2)
{
if(lazy[i1][0].second>lazy[i1][1].second&&lazy[i1][0].first==1)lazy[i1][0].second=lazy[i1][1].second;
else if(lazy[i1][0].second<lazy[i1][1].second&&lazy[i1][0].first==2)lazy[i1][0].second=lazy[i1][1].second;
}
}
}
void update(int i,int l,int r,int tl,int tr,int k,int k1)
{
if(l>r||tl>r||l>tr)
{
return;
}
if(!lazy[i].empty())
{
if(l==r)
{
smeni(i,l);
}
else
{
add(i,i*2);
add(i,i*2+1);
lazy[i].clear();
}
}
if(tl<=l&&r<=tr)
{
lazy[i].push_back({k,k1});
return;
}
int m=(l+r)/2;
update(i*2,l,m,tl,tr,k,k1);
update(i*2+1,m+1,r,tl,tr,k,k1);
}
void najdi(int i,int l,int r)
{
if(!lazy[i].empty())
{
if(l==r)
{
smeni(i,l);
}
else
{
add(i,i*2);
add(i,i*2+1);
lazy[i].clear();
}
}
if(l==r)return;
int m=(l+r)/2;
najdi(i*2,l,m);
najdi(i*2+1,m+1,r);
}
void buildWall(int n, int m, int op[], int left[], int right[],int height[], int finalHeight[])
{
v.resize(n);
int a,b,c,d;
for(int i=0;i<m;i++)
{
a=op[i];
b=left[i];
c=right[i];
d=height[i];
update(1,0,n-1,b,c,a,d);
}
najdi(1,0,n-1);
for(int i=0;i<n;i++)finalHeight[i]=v[i];
}
