/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
int RIGHT=2097152;
int d[5000000], g[5000000];
int N, K;
void update(int l, int r, int p, int h, int n, int a, int b)
{
if(b<l || r<a)
return;
if(l<=a && b<=r)
{
if(p==1) //add
{
d[n]=max(d[n], h);
g[n]=max(g[n], h);
}
if(p==2) //remove
{
d[n]=min(d[n], h);
g[n]=min(g[n], h);
}
return;
}
d[2*n]=max(min(d[2*n], d[n]), g[n]);
g[2*n]=min(max(g[2*n], g[n]), d[n]);
d[2*n+1]=max(min(d[2*n+1], d[n]), g[n]);
g[2*n+1]=min(max(g[2*n+1], g[n]), d[n]);
d[n]=10000000;
g[n]=0;
int mid=(a+b)/2;
update(l, r, p, h, 2*n, a, mid);
update(l, r, p, h, 2*n+1, mid+1, b);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
N=n, K=k;
for(int i=0; i<K; i++)
{
int p, l, r, h;
cin>>p>>l>>r>>h;
p=op[i];
l=left[i];
r=right[i];
h=height[i];
update(l+1, r+1, p, h, 1, 1, RIGHT);
}
for(int i=1; i<=RIGHT-1; i++)
{
d[2*i]=max(min(d[2*i], d[i]), g[i]);
g[2*i]=min(max(g[2*i], g[i]), d[i]);
d[2*i+1]=max(min(d[2*i+1], d[i]), g[i]);
g[2*i+1]=min(max(g[2*i+1], g[i]), d[i]);
}
for(int i=RIGHT; i<=RIGHT+N-1; i++)
{
finalHeight[i-RIGHT]=min(d[i],g[i]);
}
}
/*int main()
{
cin>>N>>K;
for(int i=1; i<=K; i++)
{
int p, l, r, h;
cin>>p>>l>>r>>h;
update(l+1, r+1, p, h, 1, 1, RIGHT);
}
for(int i=1; i<=RIGHT-1; i++)
{
d[2*i]=max(min(d[2*i], d[i]), g[i]);
g[2*i]=min(max(g[2*i], g[i]), d[i]);
d[2*i+1]=max(min(d[2*i+1], d[i]), g[i]);
g[2*i+1]=min(max(g[2*i+1], g[i]), d[i]);
}
for(int i=RIGHT; i<=RIGHT+N-1; i++)
cout<<min(d[i],g[i])<<"\n";
}*/
