#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream be("arbint.in");
ofstream ki("arbint.out");

int n,m;
class Node
{
public:
    int b,j;
    int MAX;
}T[500001];

int s[500001];

void kiir()
{
    int j = 1;
    while(T[j].MAX !=0)
    {
        cout<<j<<" -> ["<<T[j].b<<" , "<<T[j].j<<"] ==> MAX = "<<T[j].MAX<<endl;
        j++;
    }
    cout<<endl;
}

void create_tree(int now, int b, int j)
{
    T[now].b = b;
    T[now].j = j;
    if(b != j)
    {
        create_tree(now * 2, b, (b + j)/2 );
        create_tree(now * 2 + 1, (b + j) / 2 + 1, j);
        T[now].MAX = max(T[now * 2].MAX, T[now * 2 + 1].MAX);
    }
    else
    {
        be>>T[now].MAX;
        s[ b ] = now; /// b == j !!! TRIVIALIS ELEM
    }
}

void recreate_tree(int now)
{
    int NEW_MAX = max(T[now * 2].MAX, T[now * 2 + 1].MAX);
    if(T[now].MAX != NEW_MAX)
    {
        T[now].MAX = NEW_MAX;
        recreate_tree(now/2);
    }
}

void version1(int a, int b)/// T[a] = b;
{
    T[s[a]].MAX = b;
    recreate_tree(s[a]/2);
}

int BEST;
int BAL,JOBB;

void keres(int now)
{
    if(BAL <= T[now].b and T[now].j <= JOBB) ///NEM MEGY TOVABB, MIVEL MAR MINDEN FIA BELE VAN SZAMITVA
    {
        if(BEST < T[now].MAX)
            BEST = T[now].MAX;
    }
    else
    {
        if( BAL <= (T[now].b + T[now].j)/2 )
            keres(now * 2);
        if( (T[now].b + T[now].j)/2 < JOBB )
            keres(now * 2 + 1);
    }

}

void version2(int a, int b)
{
    BEST = 0;
    BAL = a;
    JOBB = b;
    keres(1);
    ki<<BEST<<endl;
}

int main()
{
    be>>n>>m;

    create_tree(1,1,n);
    //kiir();

    for(int i = 0; i < m; i++)
    {
        int version,a,b;
        be>>version>>a>>b;
        if(version == 1)/// T[a] = b;
            version1(a, b);
        else
            version2(a,b);
    }
    return 0;
}