#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ifstream fin {"aib.in"};
ofstream fout {"aib.out"};

const int Nmax = (1<<17)+55;
int N, M, sstep, aib[Nmax];

void aib_add(int pos, int val) {
  while(pos <= N) {
    aib[pos] += val;
    pos += pos & -pos;
  }
}

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

int aib_bisearch(int val) {
  int pos = 0;
  int sum = 0;
  for(int step = sstep; step; step /= 2) {
    if (pos+step <= N && sum + aib[pos+step] <= val) {
      sum += aib[pos+step];
      pos += step;
    }
  }
  if (pos == 0 || sum != val) {
    return -1;
  } else {
    return pos;
  }
}

int main(void) {
  // freopen("aib.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int a, b, q;
  fin >> N >> M;
  sstep = 1;
  while (sstep < N) { sstep *= 2; }
  rep(i, N) {
    fin >> a;
    aib_add(i+1, a);
  }
  rep(i, M) {
    fin >> q;

    switch (q) {
      case 0:
        fin >> a >> b;
        aib_add(a, b);
        break;
      case 1:
        fin >> a >> b;
        fout << aib_query(b) - aib_query(a-1) << '\n';
        break;
      case 2:
        fin >> a;
        fout << aib_bisearch(a) << '\n';
        break;
    }
  }

  return 0;
}