#include <fstream>
#define zeros(x) ((x^(x-1))&x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int aib[100003],n;
inline void adaug(int poz,int val)
{
    for(int i=poz;i<=n;i+=zeros(i))
    {
        aib[i]+=val;
    }
}
inline int sum(int poz)
{
    int s=0;
    for(int i=poz;i;i-=zeros(i))
        s+=aib[i];
    return s;
}
inline int cauta(int poz)
{
    int i,step;
    for(step=1;step<=n;step<<=1);
    for(i=0;step;step>>=1)
    {
        if(i+step<=n and poz>=aib[i+step])
        {
            i+=step;
            poz-=aib[i];
            if(poz==0)
                return i;
        }
    }
    return -1;
}
int main()
{
    int i,m,x,op,b,a,k;
    f>>n;
    f>>m;
    for(i=1;i<=n;i++)
    {
        f>>x;
        adaug(i,x);
    }
    for(i=1;i<=m;i++)
    {
        f>>op;
        if(op==0)
        {
            f>>a>>b;
            adaug(a,b);
        }
        else
            if(op==1)
            {
                f>>a>>b;
                g<<sum(b)-sum(a-1)<<'\n';
            }
            else
            {
               // g<<(1<<4);
                f>>a;
                k=cauta(a);
                g<<k<<'\n';
            }
    }
    return 0;
}