#include<fstream>
using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

const int NMAX=100005;

int n,m,AIB[NMAX];

inline int zeros(int x)
{
    return x&(x^(x-1));
}

inline void Update(int x,int val)
{
    for (int i=x;i<=n;i+=zeros(i))
        AIB[i]+=val;
}

inline void Citire()
{
    int i,p;
    fin>>n>>m;
    for (i=1;i<=n;i++)
        {
            fin>>p;
            Update(i,p);
        }
}

inline int Compute(int x)
{
    int i,rez=0;
    for (i=x;i>0;i-=zeros(i))
        rez+=AIB[i];
    return rez;
}

int Search(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;
}
inline void SOLVE()
{
    int i,x,y,z;
    for (i=1;i<=m;i++)
        {
            fin>>x>>y;
            if (!x) {fin>>z;Update(y,z);}
            if (x==1) {fin>>z;fout<<Compute(z)-Compute(y-1)<<"\n";}
            if (x==2) fout<<Search(y)<<"\n";
        }
}

int main()
{
    Citire();
    SOLVE();
    return 0;
}