#include <fstream>

using namespace std;

ifstream cin("aib.in");
ofstream cout("aib.out");

int aib[100005];

int lsb(int x) {
  return (x & (-x));
}

void update (int x, int y, int n) {
  while ( x <= n ) {
    aib[x] += y;
    x += lsb( x );
  }
}

int query(int x) {
  int sum = 0;
  while( x > 0 ) {
    sum += aib[x];
    x -= lsb( x );
  }
  return sum;
}

signed main() {
  int n, m, i, op, a;
  cin >> n >> m;
  for ( i = 1; i <= n; i++ ) {
    cin >> a;
    update(i, a, n);
  }
  for(i = 1; i <= m; i++) {
    cin>>op;
    int x, y;
    if ( op == 0 ) {
      cin>>x>>y;
      update( x, y, n);
    }
    else if ( op == 1 ) {
      cin >> x >> y;
      cout << query( y ) - query( x - 1 )<<"\n";
    } else if ( op ==  2) {
      cin >> x;
      int st = 1, dr = n, last = -1;
      while ( st <= dr ) {
        int mij = ( st + dr ) / 2, answerQuery = query(mij);
        if(answerQuery == x) {
          last = mij;
          break;
        }
        if ( answerQuery < x ) {
          st = mij + 1;
        }
        else {
          dr = mij - 1;
        }
      }
      cout << last<<"\n";
    }
  }
  return 0;
}