#include <iostream>
#include <cstdio>

using namespace std;

int s[100005];
int n,m,x,c,a,b;

void adauga(int i, int val)
{
    for(int j=i; j<=n; j+=(j&(-j)))
        s[j]+=val;
}

int suma(int poz)
{
    int ret = 0;
    for(int i = poz; i>=1; i-=(i&(-i)))
        ret+=s[i];
    return ret;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);

    cin>>n>>m;
    for(int i=1; i<=n; ++i)
    {
        cin>>x;
        adauga(i,x);
    }

    for(int i=0; i<m; ++i)
    {
        cin>>c>>a;
        if(c<2)
        {
            cin>>b;
            if(c==0)
                adauga(a,b);
            else if(c==1)
                cout<<suma(b)-suma(a-1)<<"\n";
        }
        else{
            int st=1,dr=n,mij;
            while(st<dr){
                mij=(st+dr)/2;
                if(a<=suma(mij))
                    dr=mij;
                else
                    st=mij+1;
            }
            cout<<st<<"\n";
        }
    }

    return 0;
}