# include <cstdio>
# define NMAX 100005
# define LSB(p) ( (-p) & p )
using namespace std;

int N, M, i, AIB[NMAX], op, a, b, x;

inline void Update( int val, int poz )
{
    for( int i = poz; i <= N; i += LSB(i) )
        AIB[i] += val;
}

inline int Sum( int poz )
{
    int S = 0;
    for( int i = poz; i > 0; i -= LSB(i) )
        S += AIB[i];
    return S;
}

inline int cb( int val)
{
    int i = 1, j = N, m, x;
    while( i <= j)
    {
        m = ( i + j ) >> 1;
        x = Sum( m );
        if ( x == val ) return m;
        else if ( val < x ) j = m - 1;
                       else i = m + 1;
    }
    return -1;
}

int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);

    scanf("%d %d", &N, &M);
    for( i = 1; i <= N; ++i )
    {
        scanf("%d", &x);
        Update( x, i );
    }

    for( i = 1; i <= M; ++i )
    {
        scanf("%d", &op);
        switch( op )
        {
            case 0:
                scanf("%d %d", &a, &b);
                Update( b, a );
                break;
            case 1:
                scanf("%d %d", &a, &b);
                printf("%d\n", Sum( b ) - Sum( a - 1 ) );
                break;
            case 2:
                scanf("%d", &a);
                printf("%d\n", cb( a ) );
                break;
        }
    }
    return 0;
}