#include <stdio.h>
#include <iostream>

#define NMAX 100005
#define INF (1<<30)

#define LSB(x) ( ( - x ) & x ) //  poz celui mai nesemnificativ bit de 1 al lui x

using namespace std;

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

// Aib [x] tine intervalul [ x - 2^bit + 1 , x ] unde bit = pozitia celui mai nesemnificativ bit a lui x ( LSB (x) )

void Update ( int valoare , int pos )
{
    while ( pos <= N )

    {
        AIB [ pos ] += valoare ;
        pos += LSB ( pos ) ;
    }
}

int Query ( int a , int b )
{
    int sum1 = 0 , sum2 = 0 ;

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

    for( int i = a - 1 ; i > 0; i -= LSB(i) )
        sum2 += AIB [i];

    return sum1 - sum2  ;
}

int Query2 ( int val )  // binary_search
{
    int mij , st = 1 , dr = N ;

    while ( st <= dr )
    {
        mij = ( st + dr ) >> 1 ;
        if ( Query ( 1 , mij ) == val )
             return mij;

        if ( Query ( 1 , mij ) < val )
            st = ++ mij ;

        else
            dr = -- mij ;
    }

    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 ); // se actualizeaza arborele pentru fiecare element introdus in sir
    }

    while( M >= 1 )
    {
        scanf ( "%d " , &op ) ;

        switch( op )
        {
            case 0 : // operatia de tip 0: se adauga la elementul de pe pozitia a valoarea b
                scanf ( "%d %d " , &a , &b ) ;
                Update( b , a );
                break;
            case 1 : // operatia de tip 1: se determina suma pe intervalul [a,b]
                scanf ( "%d %d " , &a , &b ) ;
                printf ( "%d \n" , Query( a , b ) ) ;
                break;
            case 2 : // operatia de tip 2 : se determina poz minima astfel incat suma sa fie valoarea respectiva
                scanf ( "%d" , &a ) ;
                printf ( "%d \n" , Query2 ( a ) ) ;
                break ;
        }

       -- M ;
    }

    return 0;
}