#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = int;
#define vi vector<int>
const ll maxN=5e5+10;
struct node
{
ll x,y;
node operator+(const node &o)
{
node ans;
ans.x=max(x,o.x);
ans.y=min(y,o.y);
ans.x=min(ans.x,o.y);
ans.y=max(ans.y,o.x);
return ans;
}
}st[4*maxN];
void update(ll pos,ll i,ll j,ll id,ll l,ll r)
{
if(l==r)
{
st[id].x=i;
st[id].y=j;
return;
}
ll mid=l+r>>1;
if(pos<=mid) update(pos,i,j,id*2,l,mid);
else update(pos,i,j,id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
vector<int>in[maxN*4],out[maxN*4];
#define pb push_back
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
for(int i=0;i<k;i++)
{
in[left[i]].pb(i);
out[right[i]+1].pb(i);
}
for(int i=0;i<k;i++)
{
update(i,-1e7,1e7,1,0,k-1);
}
for(int i=0;i<n;i++)
{
for(auto id:in[i])
{
if(op[id]==1)
{
update(id,height[id],1e7,1,0,k-1);
}
else update(id,0,height[id],1,0,k-1);
}
for(auto id:out[i])
{
update(id,-1e7,1e7,1,0,k-1);
}
node cc={0,0};
cc=cc+st[1];
finalHeight[i]=cc.x;
}
}
/*signed main()
{
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), n);
for (i = 0; i < k; i++){
status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
assert(status == 4);
}
buildWall(n, k, op, left, right, height, finalHeight);
cout << '\n';
for (j = 0; j < n; j++)
printf("%d\n", finalHeight[j]);
return 0;
}*/
