#include <fstream>

using namespace std;

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

const int N = 1000010, M = 20000010;

int n, q, t, nru, i, v[N], l[M], r[M], rad[N], a[M], sol, nods, x, y;

void go(int st, int dr, int nod) {
    if (st == dr) {
        a[nod] = v[st];
        return;
    }
    int mij = (st + dr) >> 1;
    l[nod] = ++nods;
    go(st, mij, l[nod]);
    r[nod] = ++nods;
    go(mij+1, dr, r[nod]);
    a[nod] = max(a[l[nod]], a[r[nod]]);
}

void copy(int x, int y) {
    l[x] = l[y];
    r[x] = r[y];
    a[x] = a[y];
}

void update(int st, int dr, int nod, int on, int p, int x) {
    if (st == dr) {
        a[nod] = x;
        return;
    }
    int mij = (st + dr) >> 1;
    if (p <= mij) {
        l[nod] = ++nods;
        copy(l[nod], l[on]);
        update(st, mij, l[nod], l[on], p, x);
    } else {
        r[nod] = ++nods;
        copy(r[nod], r[on]);
        update(mij + 1, dr, r[nod], r[on], p, x);
    }
    a[nod] = max(a[l[nod]], a[r[nod]]);
}

void querry(int st, int dr, int nod, int L, int R) {
    if (st >= L && dr <= R) {
        sol = max(sol, a[nod]);
        return;
    }
    int mij = (st + dr) >> 1;
    if (L <= mij) {
        querry(st, mij, l[nod], L, R);
    }
    if (R > mij) {
        querry(mij + 1, dr, r[nod], L, R);
    }
}

int main () {
    fin >> n >> q;
    for (i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    nods = 1;
    rad[0] = 1;
    go(1, n, rad[0]);
    for (; q; --q) {
        fin >> t >> x >> y;
        if (t == 1) {
            ++nru;
            rad[nru] = ++nods;
            copy(nods, rad[nru-1]);
            update(1, n, rad[nru], rad[nru-1], x, y);
        } else {
            sol = 0;
            querry(1, n, rad[nru], x, y);
            fout << sol << "\n";
        }
    }
    return 0;
}