#include <fstream>

#define NMAX 100005
#define INF (1<<30)
#define LSB(x) ( (-x)&x )

using namespace std;

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

int N, M, i, AIB[NMAX], Tip, a, b, X;

inline void Update( int Valoare, int Pos )
{
    for( int ii = Pos; ii <= N; ii += LSB(ii) )
        AIB[ii] += Valoare;
}

inline int S( int Pos )
{
    int Suma = 0;

    for( int ii = Pos; ii > 0; ii -= LSB(ii) )
        Suma += AIB[ii];

    return Suma;
}

inline int SumaInterval( int P1, int P2 )
{
    return ( S(P2) - S(P1-1) );
}

inline int BS( int Suma )
{
    int PMin = INF, L = 1, R = N, M, SCt;

    while( L <= R )
    {
        M = (L+R)/2;
        SCt = S(M);

        if( SCt == Suma )
        {
            if( PMin > M ) PMin = M;
            break;
        }
        else if( SCt < Suma ) L = M+1;
        else R = M-1;
    }

    if( PMin == INF ) return -1;
    return PMin;
}

int main()
{
    in >> N >> M;
    for( i = 1; i <= N; i++ )
    {
        in >> X;
        Update( X, i );
    }

    while( M-- )
    {
        in >> Tip;

        switch( Tip )
        {
            case 0:
                in >> a >> b;
                Update( b, a );
                break;
            case 1:
                in >> a >> b;
                out << SumaInterval( a, b ) << '\n';
                break;
            case 2:
                in >> a;
                out << BS( a ) << '\n';
                break;
        }
    }

    return 0;
}