#include <fstream>

using namespace std;
int aib[100005];
int n,m;
void update(int i,int val)
{
      while(i<=n)
      {
            aib[i]+=val;
            i+=(i&-i);
      }
}
int ps(int i)
{
      int sum=0;
      while(i>0)
      {
            sum+=aib[i];
            i-=(i&-i);
      }
      return sum;
}
int rs(int i,int j)
{
      return ps(j)-ps(i-1);
}
int cb(int a,int b,int val)
{
      int m=(a+b)/2;
      if(a>b)return -1;
      int r=ps(m);
      if(r==val)return m;
      if(r>val)return cb(a,m-1,val);
      return cb(m+1,b,val);
}
int main()
{
      ifstream cin("aib.in");
      ofstream cout("aib.out");
    int a,b,c;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
          cin>>a;
          update(i,a);
    }
    for(int j=1;j<=m;j++)
    {
          cin>>c>>a;
          if(c==0)
          {
                cin>>b;
                update(a,b);
          }
          if(c==1)
          {
                cin>>b;
                cout<<rs(a,b)<<'\n';
          }
          if(c==2)
          {
                cout<<cb(1,n,a)<<'\n';
          }
    }
    return 0;
}