#include <cstdio>
#include <cstdlib>

using namespace std ;

short nrOperatii , nrFrunze ;
short arbore [ 600001 ] ;

void citireStart ( ) ;

void construireArbore ( ) ;

void optiunea0 ( ) ;

void optiunea1 ( ) ;

void optiunea2 ( ) ;

void infundArbore ( short , short , short , short , short ) ;

short extragSuma ( short , short , short , short , short ) ;

short extragPozitie ( short , short , short , short  ) ;

inline short &max ( short &A , short &B )
{
  return ( A > B ) ? A : B ;
}

inline short &min ( short &A , short &B )
{
  return ( A > B ) ? B : A ;
}

int main ( )
{
  freopen ( "aib.in" , "r" , stdin ) ;
  freopen ( "aib.out" , "w" , stdout ) ;
  short opt ;
  citireStart ( ) ;
  construireArbore ( ) ;
  for ( short i = 0 ; i < nrOperatii ; ++i ) 
  {
    scanf ( "%hd" , &opt ) ;
    switch ( opt )
    {
      case 0 :
      {
	optiunea0 ( ) ;
	break ;
      }
      case 1 :
      {
	optiunea1 ( ) ;
	break ;
      }
      case 2 : 
      {
	optiunea2 ( ) ;
	break ;
      }
    }
  }
  return 0 ;
}

void citireStart ( ) 
{
  scanf ( "%hd%hd" , &nrFrunze , &nrOperatii ) ;
  return ;
}

void construireArbore ( )
{
  short val ;
  for ( short i = 1 ; i <=nrFrunze ; ++i )
  {
    scanf ( "%hd" , &val ) ;
    infundArbore ( i , val , 1 , nrFrunze , 1 ) ;
  }
  return ;
}

void infundArbore ( short Poz , short Val , short St , short Dr , short Index )
{
  if ( St == Dr )
  {
    arbore [ Index ] += Val ;
    return ;
  }
  if ( Poz > ( ( St + Dr ) >> 1 ) )
    infundArbore ( Poz , Val , ( ( St + Dr ) >> 1 ) + 1 , Dr , ( Index << 1 ) + 1 ) ;
  else
    infundArbore ( Poz , Val , St , ( St + Dr ) >> 1 , Index << 1 ) ;
  arbore [ Index ] = arbore [ Index << 1 ] + arbore [ ( Index << 1 ) + 1 ] ;
  return ;
}

void optiunea0 ( )
{
  short a , b ;
  scanf ( "%hd%hd" , &a , &b ) ;
  infundArbore ( a , b , 1 , nrFrunze , 1 ) ;
}

void optiunea1 ( ) 
{
  short a , b ;
  scanf ( "%hd%hd" , &a , &b ) ;
  printf ( "%hd\n" , extragSuma ( a , b , 1 , nrFrunze , 1 ) ) ;
  return ;
}

short extragSuma ( short maxSt , short maxDr , short St , short Dr , short Index )
{
  if ( ( maxSt > Dr ) || ( St > maxDr ) )
    return 0 ;
  if ( ( St >= maxSt ) && ( maxDr >= Dr ) )
    return arbore [ Index ] ;
  short mid = St + Dr ;
  mid >>= 1 ;
  short index = Index << 1 ;
  return extragSuma ( maxSt , maxDr , St , mid++ , index++ ) + extragSuma( maxSt , maxDr , mid , Dr , index ) ;
}

void optiunea2 ( )
{
  short a ;
  scanf ( "%hd" , &a ) ;
  printf ( "%hd\n" , extragPozitie ( a , 1 , nrFrunze , 1 ) ) ;
  return ;
}

short extragPozitie ( short Suma , short St , short Dr , short Index )
{
  if ( St == Dr )
    if ( Suma == arbore [ Index ] )
      return St ;
    else
      return -1 ;
  if ( arbore [ ( Index <<= 1 ) ] < Suma )
    return extragPozitie ( Suma - arbore [ Index ] , ( ( St + Dr ) >> 1 ) + 1 , Dr , Index + 1 ) ;
  else
    return extragPozitie ( Suma , St , ( St + Dr ) >> 1 , Index ) ;
}