#include<bits/stdc++.h>
using namespace std;
ifstream fin("aib.in"); ofstream fout("aib.out");


int s[10010], aib[10010], v[10010], n, m;;



void o0(int a, int b){

 for(int i=a; i<=n; i+=(i&-i)){
     aib[i]+=b;
 }

}


total_sum(int a){
    int res=0; 
    while(a){
    res+=aib[a];
    a-=a&-a;
    }
    return res;
}



int o1(int a, int b){
return total_sum(b)-total_sum(a-1);
}



int o2(int a, int r, int l){
int m=l+r; m/=2;
int s=total_sum(m);
if(r>l){return -1;}
if(s==a){return m;}
else{
   if(s>a){return o2(a, r, m-1);}
   else{return o2(a, m+1, l);} 
}

}

int main(){

fin>>n>>m;
int p=0;
for(int i=1; i<=n;+i++){
    fin>>v[i];
    s[i]=s[i-1]+v[i];
    if(!(i&i-1)){aib[i]=s[i]; p=i;}
    else{
         aib[i]=s[i]-s[i-(i&-i)];
    }
    fout<<aib[i]<<' ';
}
fout<<"\n";

int o, a, b;
for(;m;m--){
    fin>>o;
    if(o==0){fin>>a>>b; o0(a, b);}
    if(o==1){fin>>a>>b; fout<<o1(a, b)<<"\n";}
    if(o==2){fin>>a; fout<<o2(a, 1, n)<<"\n";}
}






    return 0;
}