#include <cstdio>
#include <cstring>

#define MAXN 1000001

void update(int *AIB, int M, int index, int value) 
{
    for (; index <= M; index += index & (-index))
        AIB[index] += value;
}


int query(int *AIB, int index) 
{
    int R, i;

    for (R = 0, i = index; i > 0; i -= i & (-i))
        R += AIB[i];

    return R;
}

int bsearch(int *AIB, int start, int M, int maxStep, int value) 
{
    int step, i, R = 0;
    
    for (i = 0, step = maxStep; step; step >>= 1) 
        if (i + step <= M && AIB[i + step] <= value) {
            i += step;
            value -= AIB[i];            

            if (!value)
                return i;
        } 

    return value ? -1 : i;
}

int searchBruteforce(int *AIB, int M, int value) 
{
    int i;

    for (i = 1; i <= M; ++ i)
        if (query(AIB, i) == value)
            return i - 1;

    return -1;
}

int main() 
{
    int N, M, maxStep;
    int AIB[MAXN];
    int type, x, y, step, i;

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

    memset(AIB, 0, sizeof(AIB));
    scanf("%d %d\n", &M, &N);

    for (i = 1; i <= M; ++ i) {
        scanf("%d", &x);
        update(AIB, M, i, x);
    }

    for (maxStep = 1; maxStep < M; maxStep <<= 1);

    for (; N; -- N) {
        scanf("%d %d", &type, &x);

        switch (type) {
            case 0:
                scanf("%d", &y);
                update(AIB, M, x, y);
                break;
            case 1:
                scanf("%d", &y);
                printf("%d\n", query(AIB, y) - query(AIB, x - 1));
                break;
            case 2:
                printf("%d\n", bsearch(AIB, 1, M, maxStep, x));
                break;
            default:
                break;
        }
    }
}