#include <bits/stdc++.h>

using namespace std;
int N, M;

long long aib[150005];

void update(int pz, long long val)
{
    for(int p = pz; p <= N; p += p&(-p))
        aib[p] += val;
}

long long query(int pz) {
    long long ans = 0;

    for(int p = pz; p; p -= p&(-p))
        ans += aib[p];

    return ans;

}

int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);


    int a,b,t, pos, newx;

    scanf("%d%d", &N, &M);

    for(int i = 1; i <= N; ++i) {
        scanf("%d", &newx);
        update(i, newx);
    }

    for(int i = 1; i <= M; ++i) {
        scanf("%d", &t);
        if(t == 0) {
            scanf("%d%d", &a , &b);
            update(a, b);
            continue;
        }
        if(t == 1) {
            scanf("%d%d", &a, &b);
            printf("%lld\n", query(b) - query(a - 1));
            continue;
        }

        int li = 1, lf = N, k;
        scanf("%d", &k);
        int ans = -1;
        while(li <= lf) {
            int m = li + ((lf - li) >> 1);
            long long crt = query(m);

            if(crt == k) {
                ans = m;
                lf = m - 1;
                continue;
            }

            if(crt < k)
                li = m + 1;
            else
                lf = m - 1;
        }
        printf("%d\n", ans);
    }

    return 0;
}