#include <bits/stdc++.h>
#define N 2000005
#define ll long long int
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
// #define left lef
// #define right rig
using namespace std;
ll m,ar[N],sum,t,mn[4*N],mx[4*N];
lli lazy[4*N];
ll tree[6*N];
// int n, k, op[N], lft[N], rght[N], height[N];
ll ans[N];
// void push(int l,int r,ll ind)
// {
// if(l==r) tree[ind] = max(tree[ind],lazy[ind].fi),tree[ind] = min(tree[ind],lazy[ind].se);
// if(l!=r)
// {
// lazy[ind*2].fi = max(lazy[ind*2].fi,lazy[ind].fi),lazy[ind*2].se = max(lazy[ind*2].se,lazy[ind].fi);
// lazy[ind*2+1].fi = max(lazy[ind*2+1].fi,lazy[ind].fi),lazy[ind*2+1].se = max(lazy[ind*2+1].se,lazy[ind].fi);
// lazy[ind*2].se = min(lazy[ind*2].se,lazy[ind].se),lazy[ind*2].fi = min(lazy[ind*2].fi,lazy[ind].se);
// lazy[ind*2+1].se = min(lazy[ind*2+1].se,lazy[ind].se),lazy[ind*2+1].fi = min(lazy[ind*2+1].fi,lazy[ind].se);
// }
// lazy[ind]={-1e16,1e16};
// }
void push(int l,int r,int idx)
{
if(l==r) tree[idx] = max(tree[idx],mn[idx]),tree[idx] = min(tree[idx],mx[idx]);
else
{
mn[idx*2] = max(mn[idx*2],mn[idx]),mx[idx*2] = max(mx[idx*2],mn[idx]);
mn[idx*2+1] = max(mn[idx*2+1],mn[idx]),mx[idx*2+1] = max(mx[idx*2+1],mn[idx]);
mx[idx*2] = min(mx[idx*2],mx[idx]),mn[idx*2] = min(mn[idx*2],mx[idx]);
mx[idx*2+1] = min(mx[idx*2+1],mx[idx]),mn[idx*2+1] = min(mn[idx*2+1],mx[idx]);
}
mn[idx] = INT_MIN,mx[idx] = INT_MAX;
}
// void update(int l,int r,int idx,int t,int x,int y,int k)
// {
// push(idx,l,r);
// if(x>r or y<l) return;
// if(x<=l and y>=r)
// {
// if(t==1) lazy[idx].fi = k;
// else lazy[idx].se = k;
// push(idx,l,r);
// return;
// }
// int m = (l+r)/2;
// update(l,m,idx*2,t,x,y,k),update(m+1,r,idx*2+1,t,x,y,k);
// }
void update(int l,int r,int idx,int t,int x,int y,int k)
{
push(l,r,idx);
if(x>r or y<l) return;
if(x<=l and y>=r)
{
if(t==1) mn[idx] = k;
else mx[idx] = k;
push(l,r,idx);
return;
}
int m = (l+r)/2;
update(l,m,idx*2,t,x,y,k),update(m+1,r,idx*2+1,t,x,y,k);
}
void pushlz(int l,int r,int ind)
{
push(l,r,ind);
if(l==r) return void(ans[l] = tree[ind]);
int m = (l+r)/2;
pushlz(l,m,ind*2),pushlz(m+1,r,ind*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fo(i,0,4*N-1)
mx[i]=1e16;
fo(i,0,k-1)
update(1,n,1,op[i],left[i]+1,right[i]+1,height[i]);
pushlz(1,n,1);
fo(i,1,n)
finalHeight[i-1]=ans[i];
}
// int 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);
// for (j = 0; j < n; j++)
// printf("%d\n", finalHeight[j]);
// return 0;
// }
