#include <stdio.h>
#include <assert.h>

#define ll long long

int N, M;
ll A[100005];

void update(int x, int val)
{
    for (; x <= N; x += x^(x-1)&x)
        A[x] += val;
}

ll query(int x)
{
    ll r;
    
    for (r = 0; x; x -= x^(x-1)&x)
        r += A[x];
    return r;
}

int search(ll x)
{
    int log, p;
    
    for (log = 1; log < N; log <<= 1);
    for (p = 0; log; log >>= 1)
    {
        if (p + log > N) continue;
        if (x >= A[p + log])
            p += log, x -= A[p];
    }
    return (!x ? p : -1);
}

int main(void)
{
    int i, v, tip, a, b; ll S;
    
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);

    scanf("%d %d", &N, &M);
    assert(1 <= N && N <= 100000);
    assert(1 <= M && M <= 150000);        
    for (i = 1; i <= N; ++i)
    {
        scanf("%d", &v);
        assert(1 <= v && v <= 10000);
        update(i, v);
    }

    for (; M; --M)
    {
        scanf("%d", &tip);
        if (tip == 0)
        {
            scanf("%d %d", &a, &b);
            assert(1 <= a && a <= N);
            assert(1 <= b && b <= 10000);
            update(a, b);
        }
        else if (tip == 1)
        {
            scanf("%d %d", &a, &b);
            assert(1 <= a && a <= b && b <= N);
            printf("%lld\n", query(b) - query(a-1));
        }
        else if (tip == 2)
        {
            scanf("%lld", &S);
            assert(1 <= S && S <= ((ll)1<<31));
            printf("%d\n", search(S));
        }
    }

    return 0;
}