#include <cstdio>
#include <cassert>
#define Nmax 100005
#define InFile "aib.in"
#define OutFile "aib.out"

using namespace std;

int n, m;
int Aib[Nmax];

void read();
inline int zeros (int x) {return (x^(x-1))&x;}
void update (int,int);
int query (int);
int bsearch (int);

int main()
{
  int i, op, a, b;
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  for (i=1; i<=m; i++)
  {
    scanf ("%d ", &op);
    if (op==0)
    {
      scanf ("%d %d\n", &a, &b);
      update (a, b);
    }
    if (op==1)
    {
      scanf ("%d %d\n", &a, &b);
      printf ("%d\n", query (b)-query (a-1));
    }
    if (op==2)
    {
      scanf ("%d\n", &a);
      printf ("%d\n", bsearch (a));
    }
  }
  return 0;
}

void read()
{
  int i, val;
  scanf ("%d %d\n", &n, &m);
  for (i=1; i<=n; i++)
  {
    scanf ("%d ", &val);
    update (i, val);
  }
}

void update (int pos, int val)
{
  int i;
  for (i=pos; i<=n; i+=zeros (i))
    Aib[i]+=val;
}

int query (int pos)
{
  int i, ret=0;
  for (i=pos; i>0; i-=zeros (i))
    ret+=Aib[i];
  return ret;
}

int bsearch (int val)
{
  int st=1, dr=n, mij, p=-1, tst;
  while (st<=dr)
  {
    mij=st+(dr-st)/2;
    tst=query (mij);
    if (tst==val)
    {
      p=mij;
      dr=mij-1;
    }
    else
      if (tst>val)
        dr=mij-1;
      else
        st=mij+1;
  }
  return p;
}