#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m;
int aib[100005];
void adun(int poz,int val)
{
    int i;
    for(i=poz;i<=n;i+=(i&(-i)))
    {
        aib[i]+=val;
    }
}
void scad(int poz,int val)
{
     int i;
    for(i=poz;i<=n;i+=(i&(-i)))
    {
        aib[i]-=val;
    }
}
int suma(int x)
{
    int i,sum=0;
    for(i=x;i>=1;i-=(i&(-i)))
    {
        sum+=aib[i];
    }
    return sum;
}
int main()
{
    int i,x,c,a,b;
    f>>n>>m;
   for(i=1;i<=n;i++)
   {
       f>>x;
       adun(i,x);
   }
   for(i=1;i<=m;i++)
   {
       f>>c;
       if(c==0) {f>>a>>b;adun(a,b);}
       else if(c==1)
       {
           f>>a>>b;
           g<<suma(b)-suma(a-1)<<'\n';
       }
       else
       {
           f>>a;
           int st=1,dr=n,mij,k,t;
           while(st<=dr)
           {
               mij=(st+dr)/2;
               t=suma(mij);
               if(t==a) {k=mij;dr=mij-1;}
               else if(t<a) st=mij+1;
               else dr=mij-1;
           }
           g<<k<<'\n';
       }
   }
    return 0;
}