#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 i, step;
    
    for ( step = 1; step < N; step <<= 1 ); 
    
    for( i = 0; step; step >>= 1 )
    {
         if( i + step <= N)
         {
            if( val >= Tree[i+step] ) 
            {
                i += step, val -= Tree[i];
                if ( !val ) return i;
            }
         }
    }
    
    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;
}