#include<bits/stdc++.h>
#define NMAX 100001

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");
long long aib[NMAX],n,v[NMAX];
void precalc(){
    for(long long i=1;i<=n;i++){
        aib[i]=v[i];
        long long p=1,first=(i&(i-1));
        while(p<i-first){
            aib[i]+=aib[i-p];
            p*=2;
        }
    }
}
long long p2(long long x){
    return ((x^(x-1))&x);
}
void actualizare(long long p,long long x){
    for(long long i=p;i<=n;i=i+p2(i))
        aib[i]+=x;
}
long long suma(long long p){
    long long s=0;
    for(long long i=p;i>0;i=i-p2(i))
        s+=aib[i];
    return s;
}
long long binsearch(long long a){
    if(a==0)
        return 0;
    long long s=1,d=n,m,sum;
    while(s<d){
        m=(s+d)/2; sum=suma(m);
        if(a>sum)
            s=m+1;
        else if(a<sum)
            d=m-1;
        else
            return m;
    }
    if(suma((s+d)/2)==a)
        return (s+d)/2;
    return -1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    long long m,i,a,b,querytype;
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>v[i];
    }
    precalc();
    for(i=0;i<m;i++){
        fin>>querytype;
        if(querytype==0){
            fin>>a>>b;
            actualizare(a,b);
        }
        else if(querytype==1){
            fin>>a>>b;
            fout<<suma(b)-suma(a-1)<<'\n';
        }
        else{
            fin>>a;
            fout<<binsearch(a)<<'\n';
        }
    }
    return 0;
}