#include <fstream>
#include <vector>
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
int n,m;
vector<int> AIB;
int zeros(int x)
{
    return (x^(x-1))&x;
}
void Update1(int poz,int val)
{
    for(int i=poz;i<=n;i=i+zeros(i))
      AIB[i]=AIB[i]+val;
}
long long Compute(int poz)
{
    long long s=0;
    for(int i=poz;i>=1;i=i-zeros(i))
       s=s+AIB[i];
    return s;
}
int main()
{
    cin>>n>>m;
    int x;
    AIB.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        Update1(i,x);
    }
    for(int i=1;i<=m;i++)
    {
        int ok;
        int a,b;
        cin>>ok;
        if(ok==0)
        {
            cin>>a>>b;
            Update1(a,b);
        }
        else
          if(ok==1)
          {
            cin>>a>>b;
            cout<<Compute(b)-Compute(a-1)<<'\n';
          }
        else
          {
              cin>>a;
              int poz=-1,st=1,dr=n;
              while(st<=dr)
              {
                  int mij=st+(dr-st)/2;
                  int suma=Compute(mij);
                  if(suma==a)
                     poz=mij;
                  if(suma>=a)
                      dr=mij-1;
                  else
                       st=mij+1;
              }
              cout<<poz<<'\n';
              continue;
          }
    }
    return 0;
}