#include <fstream>

using namespace std;

const int NMAX= 100000;

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

int aib[NMAX+1], N, M;

inline int lsb( int x )
{
    return x&-x;
}

void update(int pos, int val)
{
    for( int i= pos; i<=N; i+= lsb( i ) )
    {
        aib[i]+= val;
    }
}

int querry( int pos )
{
    int ans=0;

    for( int i= pos; i>0; i-= lsb( i ) )
        ans+=aib[i];

    return ans;
}

int binary( int pos )
{
    int ans=0, sc=0;

    for( int k=1<<15; k>0; k>>=1 )
    {
        if( ans + k<=N && sc + aib[ans+k]<=pos )
        {
            ans+= k;
            sc+= aib[ans];
        }
    }

    if( sc!=pos || ans==0 )
        return -1;

    return ans;
}

int main()
{
    in >> N >> M;

    int x, y, t;

    for( int i=1; i<=N; ++i )
    {
        in >> x;
        update(i, x);
    }

    for( int i= 0; i<M; ++i )
    {
        in >> t;

        if( t==0 )
        {
            in >> x >> y;
            update( x, y );
        }
        else if( t==1 )
        {
            in >> x >> y;
            out << querry(y) - querry(x-1) << '\n';
        }
        else if( t==2 )
        {
            in >> x;
            out << binary( x ) << '\n';
        }
    }
    return 0;
}