#include <cassert>
#include <cstring>
#include <queue>
#include <algorithm>
#include <bitset>
#include <set>
#include <cmath>
#include <iomanip>
#include <map>
#include <stack>
#include <vector>
#include <bitset>
#include <fstream>
// #include <iostream>

using namespace std;

#define f cin
#define g cout
#define FOR(i, a, n) for (int i = a; i <= n; ++i)
#define ROF(i, a, n) for (int i = n; i >= a; i--)
#define FIT(i, v) for (auto &i : v)
#define pb push_back
#define mp make_pair
#define mt make_touple
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 1000000007;
ll powmod(ll a, ll b) {ll res=1; a %= mod; assert(b >= 0); for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}

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

const int N = 1000100;
const int NM = 20000100;

int l[NM], r[NM], R[N], H[NM], sol, v[N], n, q, tip, nods;

void go(int nod, int st, int dr) {
    if (st == dr) {
        H[nod] = v[st];
        return;
    }
    int mij = (st + dr) >> 1;
    l[nod] = ++nods;
    go(l[nod], st, mij);
    r[nod] = ++nods;
    go(r[nod], mij+1, dr);
    H[nod] = max(H[l[nod]], H[r[nod]]);
}
void cpy(int a, int b) {
    l[a] = l[b];
    r[a] = r[b];
    H[a] = H[b];
}
void upd(int oldnod, int nod, int st, int dr, int p, int x) {
    if (st == dr) {
        H[nod] = x;
        return;
    }
    int mij = (st + dr) >> 1;
    if (p <= mij) {
        l[nod] = ++nods;
        cpy(l[nod], l[oldnod]);
        upd(l[oldnod], l[nod], st, mij, p, x);
    } else {
        r[nod] = ++nods;
        cpy(r[nod], r[oldnod]);
        upd(r[oldnod], r[nod], mij + 1, dr, p, x);
    }
    H[nod] = max(H[l[nod]], H[r[nod]]);
}
void qry(int nod, int st, int dr, int L, int R) {
    if (st >= L && dr <= R) {
        sol = max(sol, H[nod]);
        return;
    }
    int mij = (st + dr) >> 1;
    if (L <= mij) {
        qry(l[nod], st, mij, L, R);
    }
    if (R > mij) {
        qry(r[nod], mij + 1, dr, L, R);
    }
}
int main () {
    
    cin >> n >> q;
    FOR(i,1,n) {
        cin >> v[i];
    }
    nods = 1;
    R[0] = 1;
    
    go(R[0],1,n);
    
    int nrupd = 0;
    
    FOR(i,1,q) {
        cin >> tip;
        if (tip) {
            ++nrupd;
            R[nrupd] = ++nods;
            cpy(nods, R[nrupd-1]);
            int p, x;
            cin >> p >> x;
            upd(R[nrupd-1], R[nrupd], 1, n, p, x);
        } else {
            int left, right;
            cin >> left >> right;
            sol = 0;
            qry(R[nrupd], 1, n, left, right);
            cout << sol << "\n";
        }
    }
    return 0;
}