#include<bits/stdc++.h>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n, m, aib[100005];
int op, x, y;
void update(int val, int x)
{
  while (val <= n)
  {
    aib[val] += x;
    val = val + (val & (-val));
  }
}
int query(int x)
{
  int s = 0;
  while (x > 0)
  {
    s += aib[x];
    x = x - (x & (-x));
  }
  return s;
}
void cbin(int x)
{
  int st = 1, dr = n, sol = -1;
  while (st <= dr)
  {
    int mid = (st + dr) / 2;
    int q = query(mid);
    if (q == x)
      dr = mid - 1, sol = mid;
    else if (q < x) st = mid + 1;
    else dr = mid - 1;
  }
  fout << sol << "\n";
}
int main()
{
  fin >> n >> m;
  for (int i = 1; i <= n; ++i)
  {
    int x;
    fin >> x;
    update(i, x);
  }
  for (int i = 1; i <= m; ++i)
  {
    fin >> op;
    if (op == 0)
    {
      fin >> x >> y;
      update(x, y);
    }
    else if (op == 1)
    {
      fin >> x >> y;
      fout << query(y) - query(x - 1) << "\n";
    }
    else if (op == 2)
    {
      fin >> x;
      cbin(x);
    }
  }
  return 0;
}