/* Aplicatie la Arbori Indexati Binar
- determinarea sumei pe un interval si update-uri la elemente */

#include <fstream>

#define NMAX 100005
// formula pentru cel mai nesemnificativ bit de 1 al lui x
#define LSB(x) ( (-x)&x )

using namespace std;

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

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

inline void Update( int Valoare, int Pos )
{ // aduna valoare la elementul de pe pozitia Pos
    for( int i = Pos; i <= N; i += LSB(i) )
 // se updateaza toate intervalele care contin elementul de la pozitia data
        AIB[i] += Valoare;
}

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

    for( int i = Pos; i > 0; i -= LSB(i) )
    // se face suma pe interval
        S += AIB[i];

    return S;
}

inline int SumaInterval( int a, int b )
{
    return ( suma(b) - suma(a-1) );
}

inline int SumaMin(int a)
{
    int st=1,dr=N,m,Suma;
    while(st<=dr)
    {
        m=(st+dr)>>1;
        Suma=SumaInterval(1,m);
        if(Suma==a)
            return m;
        else
        if(Suma<a)
            st=m+1;
        else
            dr=m-1;
    }
    return -1;
}

int main()
{
    fin >> N >> M;
    for( i = 1; i <= N; i++ )
    {
        fin >> X;
    // se updateaza arborele pentru fiecare element introdus in sir
        Update( X, i );
    }

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

        switch( Tip )
        {
            case 0: // operatia de tip 0: se adauga la elementul de pe pozitia a valoarea b
                fin >> a >> b;
                Update( b, a );
                break;
            case 1: // operatia de tip 1: se determina suma pe intervalul [a,b]
                fin >> a >> b;
                fout << SumaInterval( a, b ) << '\n';
                break;
            case 2: // operatia de tip 2: se determina un interval [1,b] cu suma a,
                    // sau -1, daca nu exista intervalul
                fin>>a;
                fout<<SumaMin(a)<<'\n';
                break;
        }
    }

    return 0;
}