#include <stdio.h>

#define Nmax 101010
/*
0..255
256..511
etc...
*/

#define f(x) ((x)>>K)

#define K 1
#define KKK (1<<K)
#define XXX ((KKK)-1)

int t[Nmax], max[Nmax>>K];

void up(int i,int val)
{
     if (t[i]!=max[f(i)])
     {
        t[i] = val;
        if (val > max[f(i)])
        max[f(i)] = val;                 
     }
        else
     {
        t[i] = val;
        int tmp=f(i);
        max[f(i)] = -1;
        for (i=f(i)<<K;f(i) == tmp;++i)
        if(max[tmp] < t[i]) max[tmp]=t[i];            
     }     
}


int q(int a,int b)
{
    int ret = -1;
    for (;a%KKK!=0 && a<=b;++a)
    if (t[a] > ret) ret = t[a];
    for (;b%KKK!=XXX && a<=b;--b)
    if (t[b] > ret) ret = t[b];
    for (;a<=b;a+=KKK)
    if (max[f(a)] > ret) ret = max[f(a)];
    return ret;   
}



int main()
{
    freopen("arbint.in","r",stdin);
    freopen("arbint.out","w",stdout);   
    
    
    int n = 10,Q,tmp;
    
    scanf("%d%d",&n,&Q);
    
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&tmp);
        up(i,tmp);
    }
    
    for (int ii=1;ii<=100;++ii)
    {
        int x,a,b;
        scanf("%d", &x);    
        if (x==3)
        {
           for (int i=1;i<=n;++i)
           printf("%d ", t[i]);
           printf("\n");
           for (int i=0;(i<<K) <= n;++i)
           printf("%d ", max[i]);
           printf("\n");                    
        }
        else if(x==1)
        {
             scanf("%d%d", &a,&b);
             up(a,b);    
        }
        else
        {
             scanf("%d%d", &a,&b);
             printf("%d\n",q(a,b));    
        }
    }
    
    
    
    return 0;    
}