#include <stdio.h>

int BIT[100001], N;

void add(int index, int value);
int query(int index);
int search(int value);

int main()
{
	FILE *in = fopen("aib.in", "r");
	FILE *out = fopen("aib.out", "w");
    int m, op, a, b;

    fscanf(in, "%d %d", &N, &m);
    for(a = 1; a <= N; a ++)
        fscanf(in, "%d", &b),
        add(a, b);

    for(; m; m--)
    {
        fscanf(in, "%d", &op);
        switch(op)
        {
            case 0:
                fscanf(in, "%d %d", &a, &b);
                add(a, b);
                break;
            case 1:
                fscanf(in, "%d %d", &a, &b);
                fprintf(out, "%d\n", query(b) - query(a - 1));
                break;
            default:
                fscanf(in, "%d", &a);
                fprintf(out, "%d\n", search(a));
        }
	}
    
    fclose(in);
	fclose(out);
	return 0;
}

void add(int index, int value)
{
    int i = 0;
    while(index <= N)
    {
        BIT[index] += value;
        for(; !((1 << i) & index); i++);
        index += (1 << i);
    }
}

int query(int index)// searches interval [1, r]
{
    int i = 0, sum = 0;
    while(index)
    {
        sum += BIT[index];
        for(; !((1 << i) & index); i++);
        index -= (1 << i);
    }

    return sum;
}

int search(int value)
{
    int i, step;
    for(step = 1; step < N; step <<= 1);

    for(i = 0; step; step >>= 1)
        if(i + step <= N && BIT[i + step] <= value)
        {
            i += step;
            value -= BIT[i];
            if(!value) return i;
        }

    return -1;
}