#include <fstream>

#define MAXN 100005

#pragma GCC optimize("O0")

int aib[MAXN];

int query(int pos) {
  int ans = 0;
  while (pos) {
    ans += aib[pos];
    pos -= pos & (-pos);
  }
  return ans;
}

void update(int pos, int val, const int &nrn) {
  while (pos <= nrn) {
    aib[pos] += val;
    pos += pos & (-pos);
  }
}

inline int interval(int pos1, int pos2) {
  return query(pos2) - query(pos1 - 1);
}

int main() {
  std::ifstream fin("aib.in");
  std::ofstream fout("aib.out");
  int nrn, nrm, num, type, pos;
  int pos1, pos2;
  int put2, copy;
  fin >> nrn >> nrm;
  // precalculam cea mai mare putere a lui 2 <= nrn
  for (put2 = 1; put2 <= nrn; put2 <<= 1)
    ;
  put2 >>= 1;
  for (int index = 1; index <= nrn; index++) {
    fin >> num;
    update(index, num, nrn);
  }
  for (int index = 0; index < nrm; index++) {
    fin >> type;
    if (type == 0) {
      // Update
      fin >> pos >> num;
      update(pos, num, nrn);
    } else if (type == 1) {
      // Query 1
      fin >> pos1 >> pos2;
      fout << interval(pos1, pos2) << std::endl;
    } else {
      // Query 2
      fin >> num;
      // solutie in O(log(N)) folosind structura AIB-ului
      pos = 0;
      copy = put2;
      while (copy) {
        if (pos + copy <= nrn && aib[pos + copy] <= num) {
          pos += copy;
          num -= aib[pos];
        }
        copy >>= 1;
      }
      if (num == 0) {
        fout << pos;
      } else {
        fout << -1;
      }
      // Solutie initiala, cautare binara, O(log^2(N)) total
      /*pos1 = 1;
      pos2 = nrn + 1;
      while (pos2 - pos1 > 1) {
        int mij = (pos1 + pos2) / 2;
        if (query(mij) <= num)
          pos1 = mij;
        else
          pos2 = mij;
      }
      if (query(pos1) == num)
        fout << pos1;
      else
        fout << -1;*/
      fout << std::endl;
    }
  }
}