#include <bits/stdc++.h>
#define zeros(x) ((x ^ (x - 1)) & x)

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n, m;
int aib[100001];

void update(int position, int value)
{
  for(int i = position;i <= n;i += zeros(i))
    aib[i] += value;
}

int find_1(int position)
{
  int sum = aib[position];
  int parent = position - zeros(position);

  for(int i = position - 1;i != parent;i -= zeros(i))
    sum -= aib[i];

  return sum;
}

int query_sum(int position)
{
  int sum = 0;
  for(int i = position;i > 0;i -= zeros(i))
    sum += aib[i];

  return sum;
}

int find_position(int value)
{
  int rep;
  for(rep = 1;rep < n;rep <<= 1);
  for(int i = 0;rep;rep >>= 1)
    if(i + rep <= n && aib[i + rep] <= value)
      {
        i += rep;
        value -= aib[i];
        if(!value)
          return i;
      }
  return -1;
}

void read()
{
  f>>n>>m;
  int x;
  for(int i = 1;i <= n;++i)
    f>>x, update(i, x);
}

void solve()
{
  int x, y, z;
  for(int i = 1;i <= m;++i)
    {
      f>>x>>y;
      if(!x)
        f>>z, update(y, z);
      else if(x == 1)
        f>>z, g<<(query_sum(z) - query_sum(y - 1))<<'\n';
      else
        g<<find_position(y)<<'\n';
    }
}

int main()
{
  read();
  solve();
  return 0;
}