#include <iostream>

int N, T;
int tests[150001][3];
int BIT[100005];

FILE *in=fopen("aib.in","r"), *out=fopen("aib.out", "w");

int get_sum(int i){

    int j = i;
    int s = 0;
    while(j > 0){
        s += BIT[j];
        j = j - (j & (-j));
    }
    return s;
}

void add(int index, int val){

    int j = index;
    while(j <= N){
        BIT[j] += val;
        j = j + (j & (-j));
    }
}

void read()
{
    fscanf(in, "%d %d", &N, &T);

    for(int i=1; i<=N; ++i)
    {
        int val;
        fscanf(in, "%d", &val);
        add(i, val);
    }

    for(int i=0; i<T; ++i)
    {
        fscanf(in, "%d", &tests[i][0]);

        if(tests[i][0] == 0 || tests[i][0] == 1){
            fscanf(in, "%d %d", &tests[i][1], &tests[i][2]);
        }
        else {
            fscanf(in, "%d", &tests[i][1]);
        }
    }
}

int main()
{
    read();

    // Execute queries
    for(int i=0; i<T; ++i)
    {
        if(tests[i][0] == 0){
            add(tests[i][1], tests[i][2]);
        }
        else if(tests[i][0] == 1){
            int a = tests[i][1];
            int b = tests[i][2];
            int res;
            if(a == 1)
                res = get_sum(b);
            else
                res = get_sum(b) - get_sum(a-1);

            fprintf(out, "%d\n", res);
        }
        else if(tests[i][0] == 2){
            int a = tests[i][1];

            int ss = BIT[1], exp = 1;
            while(ss < a){
                exp *= 2;
                ss = BIT[exp];
            }
            if(ss==a){
                fprintf(out, "%d\n", exp);
                continue;
            }


            int j = exp/2 + 1;
            for(; j<=exp && j<=N; ++j){
                if(a == get_sum(j)){
                    fprintf(out, "%d\n", j);
                    break;
                }
            }

            if(j==exp+1 || j==N+1)
                fprintf(out, "-1\n");

        }

    }

    return 0;
}