// bril.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"

//#ifdef _msc_ver
//#define _crt_secure_no_warnings
//s#endif


#include <fstream>
#include <cstdio>
#include <stdio.h>
#include<string.h>
#include<string>
using namespace std;

#define min(a,b) (a>b?b:a)
#define max(a,b) (a<b?b:a)


//ifstream fin("arbint.in");
//ofstream fout("arbint.out");

FILE *fin, *fout;







int noduri[270010];
int n, m,a,b;
int el[100010];
char pi[18000];
int x, y, z;

void inputEl() {

    }

void splitXYZ() {
    int s = 0,p=0,t=0;
    while (pi[p] != '\n'&&pi[p]!='\0') {
        if (pi[p] == ' ') {
            if (t == 0) {
                x = s;
                s = 0;
                ++t;
                }
            else {
                a = s;
                s = 0;
                }
            }
        else
            s = 10 * s + (pi[p] - '0');
        ++p;

        }
    b = s;
    }

void inP() {
    int d = 1,s=0,k=0,i;
    while (d) {
        fgets(pi, 1 << 14, fin);
        //fin.getline(pi, 1 << 16,'\n');
        i = 0;
        while (pi[i] != '\0'&&pi[i]!='\n') {
            if (pi[i] <= '9'&&pi[i]>='0')
                s = 10 * s + (pi[i] - '0');
            else {
                ++k;
                el[k] = s;
                s = 0;
                
                }
            ++i;
            }
        if (pi[i]=='\n') {
            d = 0;
            ++k;
            el[k]=s;
            }
        }
    }


void constr(int poz, int left, int right) {
    if (left == right) {
        noduri[poz] = el[left];

        }
    else {
        int mid = (left + right) / 2;
        constr(2 * poz, left, mid);
        constr(2 * poz+1, mid+1, right);

        noduri[poz] = max(noduri[2 * poz], noduri[2 * poz + 1]);
        }
    }


void do1(int po1, int le1, int ri1) {
    while(le1!=a||ri1!=a){
        int mid = (le1 + ri1) / 2;
        if (a <= mid){
            po1=2*po1;
            ri1=mid;
            }
        else{
            po1=2*po1+1;
            le1=mid+1;
            }
        }
    noduri[po1] = b;
    po1/=2;
    while(po1!=0){
        noduri[po1] = max(noduri[2 * po1], noduri[2 * po1 + 1]);
        po1/=2;
        }
    }

int do0(int poz, int a, int b, int left, int right) {
    if (left == a&&right == b)
        return noduri[poz];
    int mid = (left + right) / 2;
    if (b <= mid)
        return do0(2*poz, a, b, left, mid);
    if (a <= mid&&b > mid)
        return max(do0(2 * poz, a, mid, left, mid), do0(2 * poz + 1,mid+1,b, mid+1, right));
    if (a > mid)
        return do0(2 * poz+1, a, b, mid+1, right);
    return 0;

    }


int main()
    {

    fin = fopen("arbint.in", "r");
    fout = fopen("arbint.out", "w");
    //fin >> n >> m;
    fscanf(fin, "%d%d", &n, &m);
    char c;
    fscanf(fin, "%c", &c);
    inP();
    constr(1,1,n);
    for (int i = 1; i <= m; ++i) {
        //fin.getline(pi,200,'\n');
        fgets(pi, 100, fin);
        splitXYZ();
        if (x == 0)
            fprintf(fout, "%d\n", do0(1, a, b, 1, n));
            //fprintf(fout, "0\n");
        //fout << do0(1, a, b, 1, n) << "\n";
        else{
            do1(1,1,n);
            }
            
        }
    fclose(fin);
    fclose(fout);
    //fin.close();
    //fout.close();
    return 0;
    }