#include<cstdio>

using namespace std;

#define INPUT "aib.in"
#define OUTPUT "aib.out"
#define PW(X) (X & (-X))
#define NMAX 100001

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

int code;
long N, M, X, Y, mid, vMid;
long A[ NMAX ], Tree[ NMAX ];

void UpdateTree(long poz, long value)
{
  while(poz <= N)
  {
    Tree[ poz ] += value;

    poz += PW(poz);
  }
}

long QueryTree(long poz)
{
  long Sum = 0;

  while(poz > 0)
  {
    Sum += Tree[ poz ];

    poz -= PW(poz);
  }

  return Sum;
}

/*long SearchTree(long value)
{
  long pLeft, pRight, middle, pMid;

  pLeft = 1;
  pRight = N;
  pMid = (pLeft + pRight) >> 1;
  middle = QueryTree(pMid);

  while(middle != value)
  {
    if(middle > value)
    {
      pRight = pMid - 1;
      pMid = (pLeft + pRight) >> 1;
      middle = QueryTree(pMid);
    }
    else
    {
      pLeft = pMid + 1;
      pMid = (pLeft + pRight) >> 1;
      middle = QueryTree(pMid);
    }
  }

  return pMid;
}*/

long SearchTree( long value, long left, long right)
{
  mid = (left + right) >> 1;
  vMid = QueryTree(mid);

  if(value < vMid)
    return SearchTree(value, left, mid - 1);
  else
  if(value > vMid)
    return SearchTree(value, mid + 1, right);
  else
    return mid;
}

void readValues()
{
  fscanf(fin, "%ld %ld", &N, &M);

  for(long i = 1; i <= N; ++i)
  {
    fscanf(fin, "%ld", &A[ i ]);

    UpdateTree(i, A[ i ]);
  }
}

void readNew()
{
  fscanf(fin, "%d", &code);

  if(code < 2)
    fscanf(fin, "%ld %ld", &X, &Y);
  else
    fscanf(fin, "%ld", &X);
}

int main()
{
  long V1, V2;

  readValues();

  for(long i = 1; i <= M; ++i)
  {
    readNew();

    if(!code)
      UpdateTree(X, Y);
    else
    if(code == 1)
    {
      V1 = QueryTree(Y);
      V2 = QueryTree(X - 1);

      fprintf(fout, "%ld\n", V1 - V2);
    }
    else
      fprintf(fout, "%ld\n", SearchTree(X, 1, N));
  } 

  fclose(fin);
  fclose(fout);

  return 0;
}