#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>

#define N_Max 100000
long long array[100000],tree[4*N_Max+5]={0};

long long max(long long a, long long b)
{
    if(a>b)
        return a;
    return b;
}

void construct_tree(long long *array,long long *tree,long long start, long long sfarsit, long long poz)
{
    if(start==sfarsit)
        {
            tree[poz]=array[start];
            return;
        }
    long long mijloc=(start+sfarsit)/2;
    construct_tree(array,tree,start,mijloc,2*poz+1);
    construct_tree(array,tree,mijloc+1,sfarsit,2*poz+2);
    tree[poz]=max(tree[2*poz+1],tree[2*poz+2]);
}

long long cautare_max(long long *tree, long long a, long long b, long long start, long long sfarsit, long long poz)
{
    if(a<=start && b>=sfarsit)
        return tree[poz];
    if(a>sfarsit || b<start)
        return -1;
    long long mijloc=(start+sfarsit)/2;
    return max(cautare_max(tree,a,b,start,mijloc,2*poz+1),cautare_max(tree,a,b,mijloc+1,sfarsit,2*poz+2));
}

int main(void)
{
    FILE* f,*g;
    long long N,M,k;
    if((f=fopen("arbin.in","r"))==NULL)
    {
        printf("fisierul de intrare nu a putut fi deschis\n");
        exit(EXIT_FAILURE);
    }
    if((g=fopen("arbin.out","w"))==NULL)
    {
        printf("fisierul de iesire nu a putut fi deschis\n");
        exit(EXIT_FAILURE);
    }
    if(fscanf(f,"%lld %lld",&N, &M)!=2)
    {
        printf("citire din fisier nereusita\n");
        exit(EXIT_FAILURE);
    }
    for(int i=1;i<=N;i++)
        fscanf(f,"%lld",&array[i]);
    for(int i=0;i<N;i++)
        printf("%lld ",array[i]);
    printf("\n");
    k=4*N;
    construct_tree(array,tree,0,N,0);
    for(int i=0;i<k;i++)
        printf("%lld ",tree[i]);
    printf("\n");
    for(int i=0;i<M;i++)
    {
        int op;
        long long a,b;
        if(fscanf(f,"%d %lld %lld",&op, &a, &b)!=3)
        {
            printf("citire din fisier nereusita\n");
            exit(EXIT_FAILURE);
        }
        if(op==0)
            fprintf(g,"%lld\n", cautare_max(tree,a,b,0,N,0));
        else
        {
            array[a]=b;
            construct_tree(array,tree,0,N,0);
        }
    }
    if(fclose(f)<0)
    {
        printf("fisierul de intrare nu a putut fi inchis\n");
        exit(EXIT_FAILURE);
    }
    if(fclose(g)<0)
    {
        printf("fisierul de iesire nu a putut fi inchis\n");
        exit(EXIT_FAILURE);
    }
    return 0;
}