#include <bits/stdc++.h>
#pragma GCC optimize("Ofast",unroll loops)
//#define ll long long
#define ll int
#define ld long double
#define i27 __int128
using namespace std;
const ll NMAX=5e5+5,NMAX2=1e9+4;
const ll TIME_MAX=9e8+5;
const ll MOD=72;
const unsigned ll MOD2=1e19;
ll get_time(){
    return chrono::steady_clock::now().time_since_epoch().count();
}
/*int v[NMAX];
bitset<NMAX> c;
//mii fr;
void ciur(){
    c[0]=c[1]=1;
    for(ll i=2;i<NMAX;i++){
        if(c[i]==0){
            //v.push_back(i);
            for(ll j=i;j<NMAX;j+=i){
                c[j]=1;
                v[j]++;
            }
        }
    }
}*/
/*ll N(ll n){
    ll d=1;
    for(ll i=0;v[i]*v[i]<=n;i++){
        ll p=0;
        while(n%v[i]==0){
            n/=v[i];
            p++;
        }
        d*=p+1;
    }
    if(n>1)
        d*=2;
    return d;
}*/
int bit[NMAX],v[NMAX];
ll npd(ll n){
    ll i;
    for(i=1;;i++){
        if((1<<i)>=n)
            break;
    }
    return (1<<i);
}
void probleme()
{
    //ciur();
    //test();
    ll n,q;
    cin>>n>>q;
    for(ll i=0;i<n;i++){
        cin>>v[i];
        for(ll j=i+1;j<NMAX;j+=j&(-j))
            bit[j]+=v[i];
    }
    n=npd(n);
    for(ll i=0;i<q;i++){
        ll cer,a,b;
        cin>>cer;
        if(cer==0){
            cin>>a>>b;
            for(ll j=a;j<=n;j+=j&(-j))
                bit[j]+=b;
        }
        if(cer==1){
            cin>>a>>b;
            a--;
            ll s1=0,s2=0;
            while(b){
                s1+=bit[b];
                b-=b&(-b);
            }
            while(a){
                s2+=bit[a];
                a-=a&(-a);
            }
            cout<<s1-s2<<'\n';
        }
        if(cer==2){
            cin>>a;
            bool notf=1;
            ll l=1,r=2*n,m,cm,sm=0;
            while(l<=r && r<=2*n){
                m=cm=(l+r)/2;
                sm=0;
                while(cm){
                    sm+=bit[cm];
                    cm-=cm&(-cm);
                }
                if(sm>a)
                    r=m-1;
                if(sm<a)
                    r+=m;
                if(sm==a){
                    cout<<m<<'\n';
                    notf=0;
                    break;
                }
            }
            if(notf==1)
                cout<<-1<<'\n';
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("thing2.in","r",stdin);
    freopen("thing2.out","w",stdout);
#else
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
#endif
    ll start=get_time();
    //ll t; cin>>t; while(t--)
    probleme();
    ll x=get_time()-start;
    cerr<<"------>secunde - "<<x/1000000000<<'\n';
    cerr<<"-->milisecunde - "<<x/1000000%1000<<'\n';
    cerr<<"->microsecunde - "<<x/1000%1000<<'\n';
    cerr<<"-->nanosecunde - "<<x%1000;
    return 0;
}