#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 val)
{
  long left, right, middle, vMid;

  left = 1;
  right = N;

  while(left <= right)
  {
    middle = (left + right) >> 1;
    vMid = QueryTree(middle);

    if(val == vMid)
      return middle;
    else
    if(val < vMid)
      right = middle - 1;
    else
    if(val > vMid)
      left = middle + 1;
  }

  return -1;
}

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));
  } 

  fclose(fin);
  fclose(fout);

  return 0;
}