#include <fstream>

using namespace std;
int a[100005], n, m;

    ofstream cout("aib.out");
void adauga(int poz, int val)
{
    while(poz<=n)
    {
        a[poz]+=val;
        poz += ((poz^(poz-1)) & poz  );
    }
}
int cat(int poz)
{
    int sum=0;
    while(poz>0)
    {
        sum += a[poz];
        poz -= ((poz^(poz-1)) & poz  );
    }
    return sum;
}
int caut_bin(int val, int li, int ls)
{
    if(ls<=li)
         return 0;
    int mij=(li+ls)/2;
    int aa = cat( mij );
    if(aa == val)
        return mij;
    else if( aa > mij )
            caut_bin(val, li, mij-1);
        else caut_bin(val, mij+1, ls);
}
int main()
{
    ifstream cin("aib.in");
    cin>>n>>m;
    for(int i = 1; i <= n ; ++ i)
    {
        int x;
        cin>>x;
        adauga(i, x);
    }
    for(int i = 1 ; i <= m ; ++ i)
    {
        int tip;
        cin>>tip;
        if(tip == 0)
        {
            int poz, val;
            cin>>poz>>val;
            adauga(poz, val);
        }
        else if(tip == 1)
        {
            int first, second;
            cin>>first>>second;
            cout<<cat(second)-cat(first-1)<<'\n';
        }
        else if(tip == 2)
        {
            int value;
            cin>>value;
            cout<<caut_bin(value, 1, n)<<'\n';
        }

    }
    return 0;
}