#include <bits/stdc++.h>

#define ub(x) (x&-x)
#define nmax 100005
#define oo (1 << 30)

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int n, m;
int a[nmax];

void add(int pos, int val)
{
  for (int i = pos; i <= n; i += ub(i))
    a[i] += val;
}

int compute(int x)
{
  int res = 0;
  for (int i = x; i > 0; i -= ub(i))
    res += a[i];
  return res;
}

void sum(int x, int y)
{
  fout <<  compute(x) - compute(y-1) << "\n";
}

void find_min_k(int a)
{
  int st = 1, dr = n;

  while (st <= dr)
  {
    int mij = (st + dr) / 2;
    int val = compute(mij);

    if (val > a) dr = mij - 1;
    else if (val < a) st = mij + 1;
    else {
      fout << mij << "\n";
      return;
    }
  }
  cout << "-1\n";
}

int main() 
{
  fin >> n >> m;

  for (int i = 1; i <= n; i ++)
  {
    int x;
    fin >> x;
    add(i, x);
  }

  for (int i = 1; i <= m; i ++)
  {
    int a, b, c;
    fin >> a >> b;
    if (a != 2)
      fin >> c;
    
    switch(a)
    {
      case 0:
        add(b, c);
        break;
      case 1:
        sum(c, b);
        break;
      case 2: 
        find_min_k(b);
        break;
    }
  }
}