#include <stdio.h>
#include <stdlib.h>

int aib[100000];

int zeros( int x ) { /// functia returneaza 2^(numarul de zerouri terminale din x );
  return ( x ^ ( x - 1 ) ) & x;
}

void add( int x, int quantity, int n ) {
  int i;
  i = x;
  while ( i <= n ) {
    aib[i] += quantity;
    i += zeros(i);
  }
}

int sum( int x ) {
  int i, s = 0;
  i = x;
  while ( i > 0 ) {
    s += aib[i];
    i -= zeros(i);
  }
  return s;
}

int search( int n, int x ) {
  int st, dr, mij, rez;
  st = 1;
  dr = n + 1;
  while ( dr - st > 1 ) {
    mij = ( st + dr ) / 2;
    if ( x >= sum(mij) )
      st = mij;
    else
      dr = mij;
  }
  if ( sum(st) == x )
    rez = st;
  else
    rez = -1;
  return rez;
}
int main() {
  FILE *fin = fopen( "aib.in", "r" ), *fout = fopen( "aib.out", "w" );
  int n, i, m, a, cer, j, j1;
  fscanf( fin, "%d%d", &n, &m );
  for ( i = 1; i <= n; i ++ ) {
    fscanf( fin, "%d", &a );
    add( i, a, n );
  }
  /**
  for ( i = 1; i <= n; i ++ ) {
    printf( "%d ", aib[i] );
  }
  **/
  for ( i = 0; i < m; i ++ ) {
    fscanf( fin, "%d", &cer );
    switch( cer ) {
    case 0:
      fscanf( fin, "%d%d", &j, &a );
      add( j, a, n );
      break;
    case 1:
      fscanf( fin, "%d%d", &j, &j1 );
      fprintf( fout, "%d\n", sum(j1) - sum(j - 1) );
      break;
    case 2:
      fscanf( fin, "%d", &a );
      fprintf( fout, "%d\n", search( n, a ) );
      break;
    }
  }
  return 0;
}