#include <bits/stdc++.h>

using namespace std;

ifstream f("arbint.in");
ofstream g("arbint.out");

int arb[400005],max1;
int gl, gr, gx, val, x, i, n, m, t,y;

void baga(int cod, int st, int dr) {
    if (st == dr) {
        arb[cod] = val;
        return;
    }
    int mij = (st+dr)/2;
    if (mij >= gx) baga(2*cod,st,mij);
    else baga(2*cod+1,mij+1,dr);
    arb[cod] = max(arb[2*cod],arb[2*cod+1]);
}

void query(int cod, int st, int dr) {
    if (gl <= st && dr<= gr) {
    cout << st << ' ' << dr <<'\n';
        max1 = max(max1, arb[cod]);
        return;
    }
    int mij = (st+dr)/2;
    if (mij>=gl) query(2*cod,st,mij);
    if (mij<gr) query(2*cod+1,mij+1,dr);
}

int main() {
    f >> n >> m;
    for (i = 1; i <= n; i++) {
        f >> x;
        gx=i,val=x;
        baga(1,1,n);
    }
    for (i = 1; i <=m;i++) {
        f >> t>>x>>y;
        if (t==0) {
            max1=0,gl=x,gr=y;
            cout<<gl<<' '<<gr<<'\n';
            query(1,1,n);
            g<<max1<<'\n';
            cout<<'\n';
            continue;
        }
        gx=x,val=y;
        baga(1,1,n);
    }
    return 0;
}