#include <stdio.h>
int n, aib[150005];
void add( int a, int b )
{
    for( ; a<=n; a+=a&-a )
        aib[a]=aib[a]+b;
}
int sum( int a )
{
    int s=0;
    for( ; a>0; a-=a&-a )
        s=s+aib[a];
    return s;
}
int caut( int val )
{
    int i, poz;
    for( poz=1; poz<n; poz<<=1 );
    for( i=0; poz; poz/=2 )
    {
        if( i+poz<=n )
        {
            if( val>=aib[i+poz] )
            {
                i+=poz;
                val-=aib[i];
                if( val==0 )
                    return i;
            }
        }
    }
    return -1;
}
int main()
{
    freopen( "aib.in", "r", stdin );
    freopen( "aib.out", "w", stdout );
    int m, op, a, b, i;
    scanf( "%d%d", &n, &m );
    for( i=1; i<=n; i++ )
    {
        scanf( "%d", &a );
        add( i, a );
    }
    for( i=1; i<=m; i++ )
    {
        scanf( "%d", &op );
        if( op==0 )
        {
            scanf( "%d%d", &a, &b );
            add( a, b );
        }
        else if( op==1 )
        {
            scanf( "%d%d", &a, &b );
            printf( "%d\n", sum(b) - sum(a - 1) );
        }
        else
        {
            scanf( "%d", &a );
            printf( "%d\n", caut(a) );
        }
    }
    return 0;
}