#include <iostream>
#include <cstdio>
#include <cmath>
#define f(x) (x&(-x))
using namespace std;
int N, M, i, j, jmax;
class BIT{
    int long long V[100001];
    int long long Query(int target){
        int out=0;
        for(j=target; j>=1; j-=f(j))
            out+=V[j];
        return out;
    }
public:
    void Add(int val, int target){
        for(j=target; j<=N; j+=f(j))
            V[j]+=val;
        return;
    }
    void Get(int a, int b){
        printf("%lld\n", Query(b)-Query(a-1));
        return;
    }
    void Find(int long long target){
        int jump, poz=0;
        for(jump=jmax; jump>=1; jump/=2){
            if(target>=V[jump+poz]){
                target-=V[jump+poz];
                poz+=jump;
            }
            if(target==0){printf("%d\n", poz); return;}
        }
        printf("-1\n");
        return;
    }
};
BIT Arb;
int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    scanf("%d%d", &N, &M);
    jmax=log2(N);
    jmax=1<<jmax;
    for(i=1; i<=N; ++i){
        int x;
        scanf("%d", &x);
        Arb.Add(x, i);
    }
    for(i=1; i<=M; ++i){
        int long long a, b, c;
        scanf("%lld", &c);
        if(c==0) {
            scanf("%lld%lld", &a, &b);
            Arb.Add(b, a);
        }
        else if(c==1){
            scanf("%lld%lld", &a, &b);
            Arb.Get(a, b);
        }
        else{
            scanf("%lld", &a);
            Arb.Find(a);
        }
    }
    return 0;
}