#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;
    const int OFF = 4;
 
    // 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+3, INIT_VALUE);
    }
 
    void operation(T &A, T B){
        if (type == 0) A += B;
        else if (type == 1) A = max(A, B);
        else A = min(A, B);
    }

    void add(T pos, T val){
        for (pos=(isReversed ? N-pos-OFF : pos+OFF);pos < N; pos += pos & (-pos))
            operation(A[pos], val);
    }
 
    T sum(T pos){
        T ans = INIT_VALUE;
        for (pos=(isReversed ? N-pos-OFF : pos+OFF);pos > 0; pos -= pos & (-pos)){
            operation(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 && A[st+p] < val) {st += p;val -= A[st];}
        return st + 1 - OFF;
    }
    #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;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        aib.add(i,x);
    }
    for (int i=1;i<=m;i++){
        int t, a, b;
        scanf("%d",&t);
        if (t==0){
            scanf("%d%d",&a,&b);
            aib.add(a,b);
        }
        else if (t==1){
            scanf("%d%d",&a,&b);
            cout << aib.sum(a,b) << '\n';
        }
        else{
            scanf("%d",&a);
            b = aib.lowerBound(a);
            if (b > n || aib.sum(b) != a) cout << "-1\n";
            else cout << b << '\n';
        }
    }
    return 0;
}