#include <fstream>

#define zeros(x) ((x^(x-1))&x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int aib[100001],n,pas,m,i,x,t,a,b;
void adauga(int val,int poz)
{
  int i;
  for (i=poz;i<=n;i+=zeros(i))
    aib[i]+=val;
}
int suma(int poz)
{
  int i,sum=0;
  for (i=poz;i>=1;i-=zeros(i))
    sum+=aib[i];
  return sum;
}
int cb(int val)
{
   int i,ans=0;
   for (ans=0,i=pas;ans+(1<<i)<=n;i--)
   {
     if (aib[ans+(1<<i)]<=val)
     {
       ans+=(1<<i);
       val-=aib[ans];
       if (val==0) return ans;
     }
   }
   return -1;
}
int main()
{
    f>>n>>m;
    for (i=1;i<=n;i++)
      f>>x,adauga(x,i);
    for (pas=1;(1<<pas)<=n;pas++);
    pas--;
    for (i=1;i<=m;i++)
    {
      f>>t;
      if (t==0)
        f>>a>>b,adauga(b,a);
      else if (t==1)
        f>>a>>b,g<<suma(b)-suma(a-1)<<'\n';
      else
        f>>a,g<<cb(a)<<'\n';
    }
    return 0;
}