#include <fstream>
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int A[Nmax],v[Nmax],n,m;

void update(int poz,int val)
{

  while(poz<=n)
  {A[poz]+=val;
   poz+=(poz&(-poz));
  }
}

int query(int poz)
{
 int s=0;
 while(poz>0)
 {
  s+=A[poz];
  poz-=(poz&(-poz));
 }
 return s;
}

int cautbin(int k)
{
  int l=1,r=n,m=(l+r)/2;
  while(l<=r)
  {
   m=(l+r)/2;
   int val=query(m);
   if(val==k) return m;
   else if(val<k) l=m+1;
   else r=m-1;
  }
  return -1;
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
      {
       int x;f>>x;
       update(i,x);
      }

    for(int i=1;i<=m;i++)
    {
     int c,x,y;
     f>>c;
     if(c==1)
     {
      f>>x>>y;
      g<<query(y)-query(x-1)<<"\n";
     }
     else if(c==0)
     {
      f>>x>>y;
      update(x,y);
     }
     else
     {
      f>>x;
      g<<cautbin(x)<<"\n";
     }
    }
    return 0;
}