#include <stdio.h>
#include <stdlib.h>
#define NMAX 100000
int aib[NMAX + 1], n;

int ub( int a ){
  //ultimul bit din dreapta
  //a&(~a+1)
  return a & ( -a );
}

void add( int i, int x ) {
  for ( ; i <= n; i += ub(i) )
    aib[i] += x;
}

int sum( int i ){
  int suma = 0;
  for ( ; i > 0; i -= ub(i) )
    suma += aib[i];
  return suma;
}

int main(){
  int m, op, i, a, b, log, lg, k;
  FILE *fin, *fout;
  fin = fopen( "aib.in", "r" );
  fout = fopen( "aib.out", "w" );
  fscanf( fin, "%d%d", &n, &m );
  for ( i = 1; i <= n; i++ ) {
    fscanf( fin, "%d", &a );
    add( i, a );
  }
  for ( i = 0; i < m; i++ ){
    fscanf( fin, "%d", &op );
    if ( op == 0 ){
      fscanf( fin, "%d%d", &a, &b );
      add( a, b );
    }
    else if ( op == 1 ) {
      fscanf( fin, "%d%d", &a, &b );
      fprintf( fout, "%d\n", sum(b) - sum(a - 1) );
    }
    else {
      fscanf( fin, "%d", &a );
      k = 0; log = 1;
      while ( log < n )
        log <<= 1;
      for ( lg = log; lg; lg >>= 1)
        if ( k + lg <= n && sum( k + lg ) <= a )
          k += lg;
      if ( sum( k ) != a )
        k = -1;
      fprintf( fout, "%d\n", k );
    }
  }
  fclose( fin );
  fclose( fout );
    return 0;
}