#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

struct Segmenttree{
    int n;
    vector<long long> node;

    Segmenttree(vector<long long> v){
        n = (int)(v.size());
        node.resize(2*n);
        for(int i=0;i<n;i++) node[i+n] = v[i];
        for(int i=n-1;i>=0;i--) node[i] = max(node[i<<1],node[i<<1|1]);
    }
    //i番目の要素をxに変更する
    void update(int i,long long x){
        i += n;
        node[i] = x;
        while(i>1){
            i >>= 1;
            node[i] = max(node[i<<1],node[i<<1|1]);
        }
    }
    //[l,r)の要素のmaxを求める
    long long query(int l,int r){
        long long res = 0;
        l += n; r += n;
        while(l<r){
            if(l&1) res = max(res,node[l++]);
            if(r&1) res = max(res,node[--r]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
    //i番目の要素にアクセス
    long long getval(int i){
        return node[i+n];
    }
};

int main(){
    int n,q;
    cin >> n >> q;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    Segmenttree seg(a);

    while(q--){
        int t,a,b;
        cin >> t >> a >> b;
        if(t==1){
            --a;
            seg.update(a,b);
        }else if(t==2){
            --a;
            cout << seg.query(a,b) << endl;
        }else if(t==3){
            --a;
            int l = a,r = n+1;
            while(r - l > 1){
                int m = (l+r)/2;
                if(seg.query(a,m)<b) l = m;
                else r = m;
            }
            cout << l+1 << endl;
        }
        /*
        rep(i,n){
            cout << seg.getval(i) << " ";
        }
        cout << endl;
        */
    }
    return 0;
}