#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<" = "<<x<<endl;
#define dbg_v(v,n) {cerr<<#v<<" = [";for(int III=0;III<=n;III++)cerr<<v[III]<<(III!=n?",":"]\n");}
#define ll long long
#define ld long double
#define pii pair<int,int>
#define MOD 1000000007
#define zeros(x) x&(x-1)^x
#define fi first
#define se second
#define Nmax 500005
using namespace std;

template<typename T = int>
struct AIB{
    #define INIT_VALUE (type == 2 ? INF : (type == 1 ? -INF : 0))
    vector<T> A;
    int N, type;
    bool isReversed;
    const T INF = 1e9;

    // type 0 = sum, 1 = max, 2 = min
    AIB(int _N = Nmax + 5,int _type = 0, bool _isReversed = false) : N(_N), type(_type), isReversed(_isReversed){
        assert(type >= 0 && type <= 2);
        A.resize(N+1, INIT_VALUE);
    }

    void add(T pos, T val){
        for (pos=(isReversed ? N-pos-4 : pos+4);pos < N; pos += pos & (-pos)){
            if (type == 0) A[pos] += val;
            else if (type == 1) A[pos] = max(A[pos], val);
            else A[pos] = min(A[pos], val);
        }
    }

    T sum(T pos){
        T ans = INIT_VALUE;
        for (pos=(isReversed ? N-pos-4 : pos+4);pos > 0; pos -= pos & (-pos)){
            if (type == 0) ans += A[pos];
            else if (type == 1) ans = max(ans, A[pos]);
            else ans = min(ans, A[pos]);
        }
        return ans;
    }

    T sum(T L, T R){
        return sum(R) - sum(L-1);
    }

    T lowerBound(T val){
        long long p = 1, st = 0;
        for (;p<N;p<<=1);
        for (;p>=1;p>>=1) if (st + p < N && sum(st+p) < val) st += p;
        if (sum(st) < val) st++;
        return st;
    }
    #undef INIT_VALUE
};
AIB<int> aib(Nmax + 5, false, false);


int main(){
    ios::sync_with_stdio(false);
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;i++){
        int x;
        cin >> x;
        aib.add(i,x);
    }
    for (int i=1;i<=m;i++){
        int t, a, b;
        cin >> t;
        if (t==0){
            cin >> a >> b;
            aib.add(a,b);
        }
        else if (t==1){
            cin >> a >> b;
            cout << aib.sum(a,b) << '\n';
        }
        else{
            cin >> a;
            b = aib.lowerBound(a);
            if (b > n || aib.sum(b) != a) cout << "-1\n";
            else cout << b << '\n';
        }
    }
    return 0;
}