#include <cstdio>

int N, M;
int v[100005];

void update(int pos, int val);
int query(int ls);
int search(int val);

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

    scanf("%d %d", &N, &M);
    for (int i=1; i<=N; ++i){
        int x;

        scanf("%d", &x);
        update(i, x);
    }
    for (int i=0; i<M; ++i){
        int op, a, b;

        scanf("%d", &op);
        switch (op){
            case 0:
                scanf("%d %d", &a, &b);
                update(a, b);
                break;
            case 1:
                scanf("%d %d", &a, &b);
                printf("%d\n", query(b)-query(a-1));
                break;
            case 2:
                scanf("%d", &a);
                printf("%d\n", search(a));
                break;
        }
    }
    return 0;
}


void update(int pos, int val){
    int p = pos;

    while (p<=N){
        v[p] += val;

        int k=1;
        for (int p_=p; !(p_&1); k<<=1, p_>>=1);
        p += k;
    }
}

int query(int ls){
    int sum = 0;

    while (ls){
        sum += v[ls];

        int k=1;
        for (int ls_=ls; !(ls_&1); k<<=1, ls_>>=1);
        ls -= k;
    }
    return sum;
}

int search(int val){
    int step;

    for (step=1; step<N; step<<=1);

    for (int i=0; step; step>>=1){
        if (i+step <= N){
            if (v[i+step] == val){
                return i+step;
            }
            else if (v[i+step] < val){
                val -= v[i+step];
                i += step;
            }
        }
    }
    return -1;
}