# include <fstream>
# define NMAX 100005
//# define LSB(p) ( (-p) & p ) // formula pentru cel mai nesemnificativ bit de 1 al lui x
# define LSB(p) (p - (p & (p-1) ) )
using namespace std;

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

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()
{
    f >> N >> M;
    for( i = 1; i <= N; ++i )
    {
        f >> x;
        Update( x, i );
    }

    for( i = 1; i <= M; ++i )
    {
        f >> op;
        switch( op )
        {
            case 0:
                f >> a >> b;
                Update( b, a );
                break;
            case 1:
                f >> a >> b;
                g << Sum( b ) - Sum( a - 1 ) << '\n';
                break;
            case 2:
                f >> a;
                g << cb( a ) << '\n';
                break;
        }
    }
    return 0;
}