#include <cstdio>
#include <algorithm>

using namespace std;

#define IN "aint.in"
#define OUT "aint.out"

int st[400004] , a[100003];
int INF = 83930212;

struct element
{
    int val , st ,dr;
}v[800004];

bool Partial_Overlap(int x , int y , int a , int b)
{
    if ( ( x <= b && x >= a ) or ( y <= b && y >= a ) or ( a <= y && a >= x ) or ( b >= x && b <= y ) )
        return 1;
    return 0;
}

bool Total_Overlap(int x , int y , int a , int b)
{
    if ( x <= a && b <= y )
        return 1;
    return 0;
}

int n , m;

void Build()
{
    int noduri , nr , i;
    noduri = 2*n-1;
    nr = 1;
    v[1].st = 1 , v[1].dr = n;
    for ( i = 1 ; i <= 4*n && nr < noduri ; i ++)
        if(v[i].st != v[i].dr ){
          v[i*2].st = v[i].st , v[i*2].dr = (v[i].st+v[i].dr)/2;
          if ( v[i*2].st == v[i*2].dr )
            v[i*2].val = a[v[i*2].st];
          v[i*2+1].st = (v[i].st+v[i].dr)/2+1 , v[i*2+1].dr = v[i].dr , nr += 2;
          if( v[i*2+1].st == v[i*2+1].dr )
            v[i*2].val = a[v[i*2+1].st];
        }


    for ( i = 4*n ; i >= 2 ; i -- )
        if ( v[i].st == 0 && v[i].dr == 0 )
          v[i].st = v[i].dr = v[i].val = INF;
        else if ( v[i].st != 0 && v[i-1].st != 0 && v[i].st != INF && v[i-1].st != INF && (i-1)%2 == 0 )
            v[i/2].val = max(v[i].val,v[i-1].val) , i -= 2 , printf ( "*%d*" , i+2 );

    for ( i = 1 ; i <= 4*n ; i ++ )
        printf ( "%d " , v[i].val );
    printf ("\n");
    for ( i = 1 ; i <= 4*n ; i ++ )
        printf ( "%d " , v[i].st );
    printf ( "\n");
    for ( i = 1 ; i <= 4*n ; i ++ )
        printf ( "%d " , v[i].dr );
    }


int main()
{
    int i , vf , x , y , V , t;

    freopen(IN,"r",stdin);
    freopen(OUT,"w",stdout);

    scanf ( "%d%d" , &n , &m );

    for ( i = 1 ; i <= n ; i ++ )
        scanf ( "%d" , &a[i] );

    Build();

    for ( i = 1 ; i <= m ; i ++ ){
        scanf ( "%d" , &V );
        scanf ( "%d%d" , &x , &y );

        if ( V == 0 )
        {
            vf = 1;
            st[vf] = 1;

            while( 1 == 1 && vf != -1)
            {
                t = st[vf];
                vf--;
                if (Partial_Overlap(v[t].st , v[t].dr , x , y))
                    st[++vf] = t*2 , st[++vf] = t*2+1;
                else if (Total_Overlap(v[t].st , v[t].dr , x , y)){
                    if ( t%2 == 0 )
                        if ( Total_Overlap(v[t+1].st,v[t+1].dr,x,y))
                           printf ( "%d" , max(v[t].val ,v[t+1].val ) );
                    vf = 1;
                    break;}


            }
        }

    }
}