#include <fstream>
#include <vector>

using namespace std;

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

class Aib {
public:
  
  Aib () {
    cin >> n;
    cin >> m;

    tree.resize (n + 1);
  
    for (int i = 1; i <= n; ++ i) {
      int k;
      cin >> k;
      Update (k, i);
    }
  }

  void Solve () {

    while (m --) {

      int type;
      cin >> type;

      if (type == 0) {
        int a, b;
        cin >> a >> b;
        Update (b, a);
      }
      else if (type == 1) {
        int a, b;
        cin >> a >> b;
        cout << Read (b) - Read (a - 1) << '\n';
      }
      else {
        int a;
        cin >> a;
        int sol = -1;

        int st = 1, dr = n;
        while (st <= dr) {

          int mid = (st + dr) >> 1;
          int cur = Read (mid);
          if (cur >= a) {
            dr = mid - 1;
            if (cur == a) {
              sol = mid;
            }
          }
          else {
            st = mid + 1;
          }
        }

        cout << sol << '\n';
      }
    }
  }

private:

  int n, m;
  vector < int > tree;
    
  int Read (int index) {

    int sum = 0;
    while (index) {
      sum += tree[index];
      index -= (index & -index);
    }
    return sum;
  }

  void Update (int val, unsigned int index) {
    
    while (index <= n) {
      tree[index] += val;
      index += (index & -index);
    }
  }
};

int main () {
  
  Aib A;
  A.Solve ();
}