#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int NN,M,S[1000005];

void op0(int i,int val)
{
  for(int j=i;j<=NN;j=j+(j&-j))
    S[j]+=val;
}

int op1(int i)
{
  int Sum=0;
  for(int j=i;j>=1;j=j-(j&-j))
    Sum+=S[j];
  return Sum;
}

int op2(int val)
{
  int Left = 1, Right = NN;

  while(Left <= Right)
  {
    int Mid = (Left + Right)/2;
    if(val==op1(Mid))
      return Mid;
    else
      if(val < op1(Mid))
        Right = Mid - 1;
      else
        Left = Mid + 1;
  }

  return -1;
}

void Read()
{
  fin>>NN>>M;
  for(int i=1;i<=NN;++i)
  {
     int x;
     fin>>x;
     op0(i,x);
  }
}

void Solve()
{
  for(int i=1;i<=M;++i)
  {
    int crt,a,b;
    fin>>crt>>a;
    if(crt<2)
      fin>>b;
    if(crt==0) op0(a,b);
    if(crt==1) fout<<(op1(b)-op1(a-1))<<"\n";
    if(crt==2) fout<<op2(a)<<"\n";
  }
}

int main()
{
    Read(); Solve();
    return 0;
}