#include <stdint.h>
#include <fstream>
#define nmax 100001
#define mmax 150001
using namespace std;
fstream f1("aib.in", ios::in);
fstream f2("aib.out", ios::out);
int32_t n, m;
int32_t aib[nmax];
///aib[x]=suma el de pe intervalul [x-2^k+1, x], unde k= cel mai nesemnif bit de 1 din
void adauga(int32_t poz, int32_t val)
{
    ///actualizezi toate intervalele ce contin poz
    while(poz<=n)
    {
        aib[poz]+=val;
        poz=2*poz- (poz&(poz-1)); ///pozitia curenta la care adaugi cea mai nesimnificativa putere de 2
    }
}
int32_t suma(int32_t x)
{
  ///vrei suma el de pe intervalul 1..x
  ///compui pe x din intervale scazand puteri ale lui 2
  int32_t sum=0;
  while(x>0)
  {
      sum+=aib[x];
      x=x& (x-1);
  }
  return sum;
}
int32_t poz_min(int32_t st, int32_t dr, int32_t sum)
{
    if(st<=dr)
    {
        int32_t mijl=st+(dr-st)/2;

        if(suma(mijl)==sum) return mijl;
        else if(suma(mijl)> sum)  return poz_min(st, mijl-1, sum);
             else return poz_min(mijl+1, dr, sum);
    }
    else return -1;
}
int main()
{
    int16_t op;
    int32_t i, va, b;
    ios_base::sync_with_stdio(false);
    f1>>n>>m;
    for(i=1; i<=n; i++)
        {
            f1>>va;
            adauga(i, va);
        }

    for(i=1; i<=m; i++)
    {
        f1>>op;
        if(!op)
        {
            f1>>va>>b;
            adauga(va, b);
        }
        else if(op==1)
        {
            f1>>va>>b;
            f2<<suma(b)-suma(va-1)<<"\n";
        }
        else
        {
            f1>>va;
            f2<< poz_min(1, n, va)<<"\n";///suma termenilor 1..k= a
            ///condtie: k= de forma 2^p pt ca aib[k]= suma(k)= suma el de la 1 la k
        }
    }

    return 0;
}