#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,aib[100005],m;
int ub(int x)
{
    return (x&(x-1))^x;
}
void upgrade (int poz,int val)
{
    int i;
    for (i=poz;i<=n;i+=ub(i))
    {
        aib[i]+=val;
    }
}
int suma (int x)
{
    int i,s=0;
    for (i=x;i>0;i-=ub(i))
    {
        s+=aib[i];
    }
    return s;
}
int cautbin(int s)
{
    int step,j;
    step=1;
    while (step<n)
    {
        step<<=1;
    }
    for (j=0;step;step>>=1)
    {
        if (j+step<=n&&suma(j+step)<=s)
        {
            j+=step;
        }
    }
    return j;
}
int i,x,p,a,b,z;
int main()
{
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        f>>x;
        upgrade(i,x);
    }
    for (i=1;i<=m;i++)
    {
        f>>p;
        if (p==0)
        {
            f>>a>>b;
            upgrade(a,b);
        }
        else
        if (p==1)
        {
            f>>a>>b;
            g<<suma(b)-suma(a-1)<<'\n';
        }
        else
        {
            f>>a;
            z=cautbin(a);
            if (suma(z)==a)
            {
                g<<z<<'\n';
            }
            else
            {
                g<<"-1"<<'\n';
            }
        }
    }
    return 0;
}