#include <fstream>

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int aib[100001],i,j,n,q,x,y,c;

void adaug(int x,int p)
{
    for(;p<=n;p+=(p^(p-1))&p)
        aib[p]+=x;
}

int query (int p)
{
    int ans=0;
    for(;p>0;p-=(p^(p-1))&p)
        ans+=aib[p];
    return ans;
}

int cautbinar(int x)
{
    int p=1,u=n,m;
    while(p<=u)
    {
        m=(p+u)/2;
        if(query(m)<x) p=m+1;
        else if(query(m)>x) u=m-1;
        else return m;
    }
    return -1;
}

int main()
{
    f>>n>>q;
    for(i=1;i<=n;i++)
    {
        f>>x;
        adaug(x,i);
    }
    for(i=1;i<=q;i++)
    {
        f>>c;
        if(c==0)
        {
            f>>x>>y;
            adaug(y,x);
        }
        else if(c==1)
        {
            f>>x>>y;
            g<<query(y)-query(x-1)<<'\n';
        }
        else
        {
            f>>x;
            g<<cautbinar(x)<<'\n';
        }
    }
    return 0;
}