#include <iostream>
#include <fstream>
#include <limits.h>
#define zeros(x) ((x^(x-1))&x)
using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int n, m;

int aib[100002];

void add(int x, int quantity){

for(int i=x; i<=n; i+=zeros(i))
    aib[i]+=quantity;

}

int compute(int x){

int s=0;
for(int i=x; i>0; i-=zeros(i))
    s+=aib[i];
return s;
}

int cautareBinara(int a, int j){

int li=1, ls=n, m=0;
int  suma=0;
    while(li<ls){
        m=(li+ls)/2;
        suma=compute(m);
        if(suma==a)
            return m;
            else if(suma>a)
                ls=m;
                else li=m+1;

    }
if(m==n-1)
    if(compute(m+1)==a)
        return m+1;

return -1;

}

void citire(){

int k, a, b;

f>>n>>m;
for(int i=1; i<=n; i++){

f>>k;
add(i, k);

}


for(int j=1; j<=m; j++){
    f>>k;
    if(k==0){

        f>>a>>b;
        add(a, b);
    }
    else if(k==1){

        f>>a>>b;

        g<<compute(b)-compute(a-1)<<"\n";


    }
    else if(k==2){

        f>>a;
        g<<cautareBinara(a, j)<<"\n";



    }}
}

int main()
{
citire();

    return 0;
}