#include<bits/stdc++.h>
using namespace std;
int n , m , treemx [8000006] , treemn [8000006];
pair < int , int > lazy [8000006];
void push ( int nod , int l , int r )
{
if ( lazy [nod] . second == 1e6 && lazy [nod] . first == -1 ) return;
treemx [nod] = min ( treemx [nod] , lazy [nod] . second );
treemn [nod] = max ( treemn [nod] , lazy [nod] . first );
if ( treemx [nod] < treemn [nod] )
{
if ( treemx [nod] == lazy [nod] . second ) treemn [nod] = treemx [nod];
if ( treemn [nod] == lazy [nod] . first ) treemx [nod] = treemn [nod];
}
if ( l != r )
{
int mx = max ( lazy [nod] . first , lazy [ nod * 2 ] . first ) , mn = min ( lazy [nod] . second , lazy [ nod * 2 ] . second );
if ( mx <= mn ) lazy [ nod * 2 ] = { mx , mn };
else
{
if ( mn == lazy [nod] . second ) lazy [ nod * 2 ] = { mn , mn };
if ( mx == lazy [nod] . first ) lazy [ nod * 2 ] = { mx , mx };
}
mx = max ( lazy [nod] . first , lazy [ nod * 2 + 1 ] . first ) , mn = min ( lazy [nod] . second , lazy [ nod * 2 + 1 ] . second );
if ( mx <= mn ) lazy [ nod * 2 + 1 ] = { mx , mn };
else
{
if ( mn == lazy [nod] . second ) lazy [ nod * 2 + 1 ] = { mn , mn };
if ( mx == lazy [nod] . first ) lazy [ nod * 2 + 1 ] = { mx , mx };
}
}
lazy [nod] = { -1 , 1e6 };
}
void bld ( int nod , int l , int r )
{
lazy [nod] = { -1 , 1e6 };
if ( l == r ) return;
int mid = ( l + r ) / 2;
bld ( nod * 2 , l , mid );
bld ( nod * 2 + 1 , mid + 1 , r );
}
void up ( int nod , int l , int r , int x , int y , int a , int b )
{
push ( nod , l , r );
if ( y < l || r < x ) return;
if ( x <= l && r <= y )
{
lazy [nod] = { a , b };
push ( nod , l , r );
return;
}
int mid = ( l + r ) / 2;
up ( nod * 2 , l , mid , x , y , a , b );
up ( nod * 2 + 1 , mid + 1 , r , x , y , a , b );
treemx [nod] = max ( treemx [ nod * 2 ] , treemx [ nod * 2 + 1 ] );
treemx [nod] = max ( treemx [nod] , max ( treemn [ nod * 2 ] , treemn [ nod * 2 + 1 ] ) );
treemn [nod] = min ( treemx [ nod * 2 ] , treemx [ nod * 2 + 1 ] );
treemn [nod] = min ( treemn [nod] , min ( treemn [ nod * 2 ] , treemn [ nod * 2 + 1 ] ) );
}
int qr ( int nod , int l , int r , int x , int y )
{
push ( nod , l , r );
if ( y < l || r < x ) return -1;
if ( x <= l && r <= y )
{
if ( l == r && treemx [nod] != treemn [nod] )
{
cout << 0 / 0;
}
return treemx [nod];
}
int mid = ( l + r ) / 2;
return max ( qr ( nod * 2 , l , mid , x , y ) , qr ( nod * 2 + 1 , mid + 1 , r , x , y ) );
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
bld ( 1 , 0 , n );
up ( 1 , 0 , n , 0 , n , 0 , 2 );
for (int i = 0; i < k; i++) {
if ( op [i] == 1 ) up ( 1 , 0 , n , left [i] , right [i] , height [i] , 1e6 );
if ( op [i] == 2 ) up ( 1 , 0 , n , left [i] , right [i] , -1 , height [i] );
}
for (int i = 0; i < n; i++) {
finalHeight[i] = qr ( 1 , 0 , n , i , i );
}
}
/*
int main()
{
scanf ( "%d%d" , &n , &m );
bld ( 1 , 0 , n );
//up ( 1 , 0 , n , 0 , n , 2 , 0 );
while ( m -- )
{
int t , l , r , x;
scanf ( "%d%d%d%d" , &t , &l , &r , &x );
if ( t == 1 ) up ( 1 , 0 , n , l , r , x , 1e6 );
if ( t == 2 ) up ( 1 , 0 , n , l , r , -1 , x );
}
for ( int i = 0 ; i < n ; i ++ ) printf ( "%d\n" , qr ( 1 , 0 , n , i , i ) );
}
*/
