#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream fin ("aib.in");
ofstream fout("aib.out");
int n,m,AIB[Nmax],k;

void update( int poz , int val )
{
  while( poz <= n )
    {
      AIB[ poz ] += val ;
      poz += ( poz & ( - poz) );
    }
}

int query ( int poz )
{
 int sum = 0 ;
 while ( poz )
    {
     sum += AIB[ poz ];
     poz -= ( poz & ( - poz) );
    }
  return sum ;
}

int query2 ( int  k  )
{
 int i , s , m  , d  , x ;
 s = 1 ;
 d = n ;
    while ( s <= d )
    {
     m =  s + ( d - s ) / 2 ;
     x = query( m );

     if ( x == k  )
        return  m ;

     if( k < x )
         d = m - 1  ;
     else
        s = m + 1 ;
    }
   return -1 ;
}

void read( )
{
 fin>>n>>m;
 int x , task , a , b ;
 for( int i = 1 ; i <= n ; i ++ )
    {
     fin>>x;
     update( i , x );
    }
 for ( int  i = 1 ; i <= m ; i++ )
    {
     fin >>task ;
     if( task == 0 )
        {
         fin >> a >> b ;
         update( a , b );
        }
     if ( task == 1 )
        {
         fin >> a >> b ;
         fout << query ( b  ) - query ( a - 1 )<<"\n";
        }
     if (task == 2 )
        {
         fin >> k ;
         fout<<query2( k )<<"\n";
        }
    }


}

int main()
{
    read();
    return 0;
}