#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
// #include <vec
#include <map>
using namespace std;

#ifdef INFOARENA
#define TEST 0
#else
#define TEST 1
#endif

class IntervalTrees {
public:
  IntervalTrees(int nums_number) {
    sums.resize(nums_number + 1, 0);
  }
  int Query(int position) {
    int sum = 0;
    while (position) {
      sum += sums[position];
      position -= position & (-position);
    }
    return sum;
  }
  int Search(int value) {
    int left = 1, right = sums.size() - 1;
    while (left + 1 < right) {
      int middle = (left + right) / 2;
      int result = Query(middle);
      if (result < value) {
        left = middle + 1;
      } else if (result > value) {
        right = middle - 1;
      } else {
        right = middle;
      }
    }
    if (Query(left) == value) {
      return left;
    } else {
      if (Query(right) == value) {
        return right;
      } else {
        return -1;
      }
    }
  }
  int Update(int position, int val) {
    while (position < sums.size()) {
      sums[position] += val;
      position += position & (-position);
    }
  }

private:
  vector<int> sums;
};

int main() {

    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int nums_number, queries_number;
    scanf("%d %d", &nums_number, &queries_number);
    IntervalTrees *instance = new IntervalTrees(nums_number);
    for (int i = 0; i < nums_number; ++i) {
      int x;
      scanf("%d", &x);
      instance->Update(i + 1, x);
    }

    for (int i = 0; i < queries_number; ++i) {
      int type, x, y;
      scanf("%d", &type);
      if (type == 0 || type == 1) {
        scanf("%d %d", &x, &y);
      } else {
        scanf("%d", &x);
      }
      if (type == 0) {
        instance->Update(x, y);
      } else if (type == 1) {
        if (x > y) {
          swap(x, y);
        }
        printf("%d\n", instance->Query(y) - instance->Query(x - 1));
      } else {
        printf("%d\n", instance->Search(x));
      }
  }

  return 0;
}