// Simionescu Andrei, 4/10/2010
// http://infoarena.ro/problema/aib
// Dificultate: MEDIUM
// Categorii: Arbori, SD (structuri date)

#include <cstdio>
#include <vector>
using namespace std;

typedef unsigned int UINT;

vector<UINT> tree;

inline UINT min( UINT x, UINT y ){ return y^( (x^y) & -(x<y) ); }

void Update( UINT, UINT );  // Will update the BIT = binary-indexed tree
UINT Sum( UINT );           // Will calculate the sum <1, x>
int Search( UINT );         // Will search for the sum <A, B> which equals x

	
int main(){
	freopen( "aib.in", "r", stdin );
	freopen( "aib.out", "w", stdout );
        
    UINT n, m, i, x, y, op;
    
    scanf( "%d %d", &n, &m );
    
    tree.resize( n+1 );
    
    for( i = 1; i <= n; ++i )
    {
        scanf( "%d", &x );
        Update( i, x );
    }
    
    for( i = 0; i < m; ++i )
    {
        scanf( "%d %d", &op, &x );
        if( op < 2 )
        {
            scanf( "%d", &y );
            if( 0 == op )
                Update( x, y );
            else printf( "%d\n", Sum(y) - Sum(x-1) );
        }
        else printf( "%d\n", Search(x) );
    }
    
    return 0;
}

void Update( UINT x, UINT y )
{
    UINT p = 0;
    for( UINT n = tree.size(); x <= n; )
    {
        tree[x] += y;
        x += ( x & -x );
    }
}

// SUM
UINT Sum( UINT x )
{
    UINT s = 0, p = 0;
    
    for( ; x > 0;  )
    {
       s += tree[x];
       x -= (x & -x );
    }
    
    return s;
}

// SEARCH
int Search( UINT x )
{
    UINT left = 1, right = tree.size() - 1, y, m, poz = right + 1;
    
    if( x == Sum(right) )
        return right;
    if( x == Sum(left ) )
        return left;
        
    while( left < right )
    {
        m = left + (right - left) / 2;
        y = Sum(m);
        if( y == x )
           poz = min( poz, m );
        if( y >= x )
            right = m;
        else left = m + 1;
    }
    if( tree.size() == poz )
        return -1;
    return poz;
}