#include <iostream>

using namespace std;

int N, T;
int v[100001];
int tests[150001][3];

int BIT[100005];

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

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

    for(int i=0; i<N; ++i)
    {
        fscanf(in, "%d", &v[i]);
        BIT[i+1] = 0;
    }

    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 get_sum(int i){

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

int main()
{
    read();

    // Create BIT
    for(int i=1; i<=N; ++i)
    {
        int s = v[i-1];
        int j = i;
        while(j <= N){
            BIT[j] += s;
            j = j + (j & (-j));
        }
    }

    // Execute queries
    for(int i=0; i<T; ++i)
    {
        if(tests[i][0] == 0){

            int j = tests[i][1];
            while(j <= N){
                BIT[j] += tests[i][2];
                j = j + (j & (-j));
            }
        }
        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;
}