#include <cstdio>

using namespace std;
int aib[100005], n ;
void update ( int poz, int val )
{
    for ( ; poz <= n ; poz += poz & -poz )
        aib[poz] += val ;
}
int query ( int poz )
{
    int s = 0 ;
    for ( ; poz ; poz -= poz & -poz )
        s += aib[poz] ;
    return s ;
}
int bs ( int a )
{
    int st = 1, dr = n, med, last = -1 ;
    while ( st <= dr )
    {
        med = ( st + dr ) / 2 ;
        if ( query ( med ) == a )
        {
            last = med ;
            dr = med - 1 ;
        }
        else if ( a < query ( med ) )
            dr = med - 1 ;
        else
            st = med + 1 ;
    }
    return last ;
}
int main()
{
    freopen ( "aib.in","r",stdin ) ;
    freopen ( "aib.out","w",stdout ) ;
    int m, i, nr, op, a, b ;
    scanf ( "%d%d",&n,&m ) ;
    for ( i = 1 ; i <= n ; i ++ )
    {
        scanf ( "%d",&nr ) ;
        update ( i, nr ) ;
    }
    for ( i = 1 ; i <= m ; i ++ )
    {
        scanf ( "%d",&op ) ;
        if ( op == 0 )
        {
            scanf ( "%d%d",&a,&b ) ;
            update ( a, b ) ;
        }
        else if ( op == 1 )
        {
            scanf ( "%d%d",&a,&b ) ;
            printf ( "%d\n",query ( b ) - query ( a - 1 ) ) ;
        }
        else
        {
            scanf ( "%d",&a ) ;
            printf ( "%d\n",bs ( a ) ) ;
        }
    }
    return 0;
}