#include <fstream>
#define maxi 100000
#define ub(x) ((x^(x-1))&x)
using namespace std;
ifstream f;
ofstream g;
int n,m,aib[maxi+10],x,op,a,b;
void UPDATE(int x,int val)
{
    for(int i=x;i<=n;i+=ub(i))
        aib[i]+=val;
    return;
}
int SUM(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=ub(i))
        sum+=aib[i];
    return sum;
}
int BINARY(int suma)
{
    int st=1,dr=n,pozmin=maxi;
    while(st<=dr)
    {
        int mid=(st+dr)>>1;
        int sum_mid=SUM(mid);
        if(sum_mid==suma)
        {
            if(pozmin>mid)
            pozmin=mid;
            dr=mid-1;
        }
        else{
            if(sum_mid<suma)
            {
                st=mid+1;
            }
            else dr=mid-1;
        }
    }
    return poz;
}
void AIB()
{
    f.open("aib.in",ios::in);
    g.open("aib.out",ios::out);
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f>>x;
        UPDATE(i,x);
    }
    for(int i=1;i<=m;i++)
    {
        f>>op;
        switch(op)
        {
            case 0:{
              f>>a>>b;
              UPDATE(a,b);
            }break;
            case 1:{
              f>>a>>b;
              g<<SUM(b)-SUM(a-1)<<'\n';
            }break;
            case 2:{
              f>>a;
              g<<BINARY(a)<<'\n';
            }break;
        }
    }
    f.close();
    g.close();
    return;
}
int main()
{
    AIB();
    return 0;
}