#include <cstdio>
#include <cstdlib>

using namespace std ;

int nrOperatii , nrFrunze ;
int arbore [ 600001 ] ;

void citireStart ( ) ;

void construireArbore ( ) ;

void optiunea0 ( ) ;

void optiunea1 ( ) ;

void optiunea2 ( ) ;

void infundArbore ( int , int , int , int , int ) ;

int extragSuma ( int , int , int , int , int ) ;

int extragPozitie ( int , int , int , int  ) ;

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

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

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

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

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

void infundArbore ( int Poz , int Val , int St , int Dr , int 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 ( )
{
  int a , b ;
  scanf ( "%d%d" , &a , &b ) ;
  infundArbore ( a , b , 1 , nrFrunze , 1 ) ;
}

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

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

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

int extragPozitie ( int Suma , int St , int Dr , int 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 ) ;
}