#include <fstream>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
long long n,v[100001],aib[100001],sol,c,x,y,p;
long long query(long long p)
{
    long long x=0;
    for(int i=p;i>=1;i-=(i&(-i)))
    {
        x+=aib[i];
    }
    return x;
}
void update(int x,int val)
{
    for(int i=x;i<=n;i+=(i&(-i)))
    {
        aib[i]+=val;
    }
}
int main()
{
    fin>>n>>p;
    for(int i=1;i<=n;i++){
        fin>>v[i];
        update(i,v[i]);
    }
    for(int i=1;i<=p;i++)
    {
        fin>>c;
        if(c==0){
            fin>>x>>y;
            update(x,y);
        }
        else if(c==1)
        {
            fin>>x>>y;
            fout<<query(y)-query(x-1)<<"\n";
        }
        else
        {
            fin>>x;
            int st=1,dr=n,poz=-1,mid=0;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(query(mid)>x)
                {

                    dr=mid-1;
                }
                else if(query(mid)<x)
                    st=mid+1;
                else
                {
                    poz=mid;
                    dr=mid-1;
                }
            }
            fout<<poz<<"\n";
        }

    }
    return 0;
}