#include <iostream>
#include <vector>
#include <fstream>
#define maxN 100000 + 5

using namespace std;

int bit[maxN], n;

void update (int x, int i){
  for(int j = i; j <= n; j += j & (-j))
    bit[j] += x;
}

int sum(int r){
  int sum = 0;

  for(int i = r; i > 0; i -= i & (-i))
    sum += bit[i];

  return sum;
}

int searc(int s){
  int m, l, r;

  l = 0;
  r = n;

  while (r - l > 1){
    m = (l + r) >> 1;
    int t = sum(m);
    if (t < s)
      l = m;
    else
      r = m;
  }
  return r;
}

int main()
{
  ifstream f("aib.in");
  ofstream g("aib.out");

  int m;
  f >> n >> m;

  for(int i = 1; i <= n; ++i){
    int x;
    f >> x;
    update(x,i);
  }
  bit[0] = 0;

  for (int i = 0; i < m; ++i){
    int x, y, z;
    f >> x;

    if(x == 0){
      f >> y >> z;
      update(z,y);
    }
    else if(x == 1){
      f >> y >> z;
      g << sum(z) - sum(y - 1) << '\n';
    }
    else{
      f >> y;
      z = searc(y);
      if(sum(z) != y)
        g << -1 << '\n';
      else
        g << z << '\n';
    }
  }

  f.close();
  g.close();

  return 0;
}