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