#include <iostream>
#include <fstream>

using namespace std;

int v[100005],bit[100057];
 int n,m;
 void update(int i,int val)
 {
     while(i<=n)
     {
         bit[i]+=val;
         i+=i&-i;
     }
 }
 int sp(int i)
 {
     int sum=0;
     while(i>0)
     {
         sum+=bit[i];
         i-=i&-i;
     }
     return sum;
 }
 int rs(int i,int j)
 {
     return sp(j)-sp(i-1);
 }
int main()
{
    ifstream cin("aib.in");
    ofstream cout("aib.out");
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
    }
    for(int i=1;i<=n;++i)
    {
        update(i,v[i]);
    }
    int caz,a,b;
    for(int i=1;i<=m;++i)
    {
        cin>>caz;
        if(caz==0)
        {
            cin>>a>>b;

            update(a,b);
        }
        else if(caz==1)
        {
            cin>>a>>b;
            cout<<rs(a,b)<<"\n";
        }
        else
        {
            cin>> a;
            int st=1,mij,nr,dr=n,in=-1;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                nr=sp(mij);
                if(nr>=a)
                {
                    in=mij;
                    dr=mij-1;
                }
                else
                {
                    st=mij+1;
                }
            }
            cout<<in<<"\n";
        }
    }
    return 0;
}