#include <fstream>

using namespace std;

int* aib;

int suma(int poz){

    int s = 0;
    while(poz){
        s += aib[poz];
        poz = poz & (poz-1);
    }
    return s;

}

int main(){

    ifstream fin("aib.in");
    ofstream fout("aib.out");

    fstream::sync_with_stdio(false);

    int n, m;
    fin>>n>>m;

    int* v = new int[n+1];
    aib = new int[n+1];

    int* suma_partiala = new int[n+1];
    suma_partiala[0] = 0;

    int ci, k, pow_of_2;

    for(int i = 1; i <= n; i++){
        fin>>v[i];
        suma_partiala[i] = suma_partiala[i-1] + v[i];
        if(i%2)
            aib[i] = v[i];
        else {
            ci = i; k = 0;
            while(ci && !(ci%2) ){
                k++;
                ci /= 2;
            }
            pow_of_2 = 1<<k;
            aib[i] = suma_partiala[i] - suma_partiala[i-pow_of_2];
        }
    }

    delete[] suma_partiala;

    int op,a,b, inc, sf;

    for(int i = 1; i <= m; i++){
        fin>>op;
        if(op == 0){
            fin>>a>>b;
            do {
              aib[a] += b;
              a += a & -a;
            } while (a <= n+1);
        } else if (op == 1){
            fin>>a>>b;
            fout<<suma(b) - suma(a-1)<<"\n";
        } else {
            bool foundIndex = false;
            fin>>a;
            inc = 1;
            sf = n;
            while(inc <= sf){
                b = (inc + sf)/2;
                int sum = suma(b);
                if(sum == a){
                    fout<<b<<"\n";
                    foundIndex = true;
                    break;
                }

                if(inc == sf){
                    fout<<-1<<"\n";
                    foundIndex = true;
                    break;
                }

                if (sum > a){
                    sf = b;
                } else if (sum < a){
                    inc = b+1;
                }

            }
            if(!foundIndex)
                fout<<-1<<"\n";
        }
    }


}