#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(const vector<int>& nums) {
    sums.resize(nums.size() + 1);
    for (int i = 0; i < nums.size(); ++i) {
      Update(i + 1, nums[i]);
    }
  }
  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;
};

struct Query {
  int type, x, y;
};

int main() {
  vector<int> nums;
  vector<Query> queries;

  if (!TEST) {
    nums = vector<int>({25,42,8,15,1,55,16,67});
    queries = vector<Query>({{0,5,12},{2,25,0},{2,90,0},{1,7,7},{1,2,8},{2,241,0}});

  } else {
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int nums_number, queries_number;
    scanf("%d %d", &nums_number, &queries_number);
    nums.resize(nums_number);
    queries.resize(queries_number);
    for (int i = 0; i < nums_number; ++i) {
      scanf("%d", &nums[i]);
    }
    for (int i = 0; i < queries_number; ++i) {
      scanf("%d", &queries[i].type);
      if (queries[i].type == 0 || queries[i].type == 1) {
        scanf("%d %d", &queries[i].x, &queries[i].y);
      } else {
        scanf("%d", &queries[i].x);
      }
    }
  }

  IntervalTrees *instance = new IntervalTrees(nums);
  for (Query query : queries) {
    if (query.type == 0) {
      instance->Update(query.x, query.y);
    } else if (query.type == 1) {
      if (query.x > query.y) {
        swap(query.x, query.y);
      }
      printf("%d\n", instance->Query(query.y) - instance->Query(query.x - 1));
    } else {
      printf("%d\n", instance->Search(query.x));
    }
  }

  return 0;
}