#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#define DIMMAX 100005
#define sqrt_DIMMAX 320
#define ll long long
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

using namespace std;

ll A[DIMMAX],op[DIMMAX][3];
ll N, M, rad;
ll smen[sqrt_DIMMAX];

void init()
{
    FOR(i,0,DIMMAX-5)
    {
        A[i]=-2;
    }
    FOR(i,0,sqrt_DIMMAX-2)
    {
        smen[i]=-3;
    }
}

ll minim(ll a, ll b)
{
    if(a<b)return a;
    else return b;
}
ll maximum(ll a, ll b)
{
    if(a>b)return a;
    else return b;
}

void citire()
{
    ifstream f("arbint.in");
    f>>N>>M;
    FOR(i,1,N)
    {
        f>>A[i];
    }
    FOR(i,1,M)
    {
        FOR(j,0,2)
        {
            f>>op[i][j];
        }
    }
    f.close();
}

     ofstream g("arbint.out");

void build_smen(ll poz)
{
    int maxim=-10, loc;
    FOR(i, (poz-1)*rad+1, poz*rad)
    {
        if(A[i]>maxim)
        {
            maxim=A[i];
            loc=i;
        }
    }
    smen[poz]=maxim;
}

void returnare(ll a, ll b)
{
    int maxim=-5;

    ll s=(a-1)/rad+1,d=(b-1)/rad+1;

    FOR(i,s+1,d-1)
    {
        if(smen[i]>maxim)maxim=smen[i];
    }

    ll mic=minim(s*rad,b);

    FOR(i,a,mic)
    {
        if(A[i]>maxim)maxim=A[i];
    }

    ll mare=maximum((d-1)*rad+1,a);

     FOR(i,mare,b)
    {
        if(A[i]>maxim)maxim=A[i];
    }

    g<<maxim<<'\n';
}

void afisare()
{
    FOR(i,1,N)
    {
        cout<<A[i]<<" ";
    }
    cout<<'\n';
    FOR(i,1,rad)
    {
        cout<<smen[i]<<" ";
    }
    cout<<'\n'<<'\n';
}

int main()
{
    init();
    citire();
    rad=sqrt(N);
    if(rad*rad!=N)rad++;

    FOR(i,1,rad)
    {
        build_smen(i);
    }

    FOR(i,1,M)
    {
        if(op[i][0]==0)
        {
            returnare(op[i][1],op[i][2]);
        }
        else
        {
            A[op[i][1]]=op[i][2];
            build_smen((op[i][1]-1)/rad+1);
        }
        //cout<<"<<"<<op[i][0]<<">>";
        afisare();

    }

    g.close();
    return 0;
}