#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,i,ret,k,a,b,c,aib[100004],t;
#define zeros(x) ( (x ^ (x - 1)) & x )
void Add(int x, int cant)
{
    int i;

    for (i=x; i<=n; i+=zeros(i))
        aib[i] += cant;
}
int suma(int x)
{
    int i, ret = 0;

    for (i=x; i>0; i-=zeros(i))
        ret+=aib[i];
    return ret;
}
int caut(int val)
{
    int i, step;

    for (step=1;step<n;step<<=1);

    for(i=0;step;step>>=1)
    {
         if(i+step<= n)
         {
            if(val>=aib[i+step])
            {
                i+=step, val-=aib[i];
                if ( !val ) return i;
            }
         }
    }

    return -1;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
        {
            f>>t;
            Add(i,t);
        }
    for(i=1;i<=m;++i)
    {
        f>>k;
        if(k<2)
        {
            f>>a>>b;
            if(k==0)
                Add(a,b);
            if(k==1)
                g<<suma(b)-suma(a-1)<<endl;
        }
        if(k==2)
        {f>>c; g<<caut(c)<<endl;}
    }

    return 0;
}