#include <iostream>
#include <fstream>
#define int long long
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int n, i, m;
int aib[100005];

void update(int p, int a){
    for(int i=p;i<=n;i+=(i&-i)){
        aib[i]+=a;
    }
}

int query(int p){
    int ans=0;

    for(int i=p;i>=1;i-=(i&-i)){
        ans+=aib[i];
    }

    return ans;
}

signed main()
{
    fin>>n>>m;

    int a, b, p, t;
    for(i=1;i<=n;i++){
        fin>>a;
        update(i, a);
    }


    for(i=1;i<=m;i++){
        fin>>t;

        if(t==0){
            fin>>p>>a;
            update(p, a);
        }
        if(t==1){
            fin>>a>>b;
            fout<<query(b)-query(a-1)<<'\n';
        }
        if(t==2){
            fin>>a;
            int st=1, dr=n, mij, ans=-1;
            while(st<=dr){
                mij=(st+dr)/2;
                if(query(mij)<a){
                    st=mij+1;
                }else if(query(mij)==a){
                    dr=mij-1;
                    ans=mij;
                }else if(query(mij)>a){
                    dr=mij-1;
                }
            }

            fout<<ans<<'\n';
        }
    }



    return 0;
}