#include <fstream>

#define zeros(x) ((x^(x-1))&x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int aib[100001],n,pi,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 Search(int v) {
  int i, p = pi;
  for (i = 0; p; p >>= 1)
    if (i + p <= n)
      if (aib[i + p] <= v) {
        i += p, v -= aib[i];
        if (v == 0)
          return i;
      }
  return -1;
}
int main()
{
    f>>n>>m;
    for (i=1;i<=n;i++)
      f>>x,adauga(x,i);
    for (pi=1;pi<n;pi<<=1);
    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<<Search(a)<<'\n';
    }
    return 0;
}