#include <fstream>

using namespace std;

ifstream fin( "aib.in" );
ofstream fout( "aib.out" );
const int NMAX = 1 << 17;
int aib[NMAX + 1];
int n;

void update( int poz, int val ){
  int i;
  for( i = poz; i <= n; i += i&(-i) )
    aib[i] += val;
}

int query( int poz ){
  int i, sum;
  sum = 0;
  for( i = poz; i > 0; i -= i&(-i) )
    sum += aib[i];
  return sum;
}

int main() {
    int t, i, x, a, b;
    fin >> n >> t;
    for( i = 1; i <= n; ++i ){
      fin >> a;
      update(i, a);
    }
    for( i = 0; i < t; ++i ){
      fin >> x >> a;
      if( x == 1 || x == 0 )
        fin >> b;
      if( x == 0 )
        update( a, b );
      else if ( x == 1 )
        fout << query( b ) - query(a - 1) << "\n";
      else{
        int st, dr, med, sol = -1;
        st = 0;
        dr = n + 1;
        while( dr - st > 1 && sol == -1 ){
          med = (st + dr) >> 1;
          if( query(med) > a )
            dr = med;
          else{
            if( query(med) == a )
              sol = med;
            st = med;
          }
        }
        fout << sol << "\n";
      }
    }
    return 0;
}