#include <fstream>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int last2(int x)
{
    return x&(x^(x-1));
}
void update(int poz, int val);
int query(int poz);

int n, m, AIB[100005];

int main()
{
    int i, tip, x, y, st, dr, mij, nr;

    fin >> n >> m;
    for (i=1;i<=n;i++)
    {
        fin >> x;
        update(i,x);
    }
    for (i=1;i<=m;i++)
    {
        fin >> tip;
        if (tip == 0)
        {
            fin >> x >> y;
            update(x,y);
        }
        else if (tip == 1)
        {
            fin >> x >> y;
            fout << query(y)-query(x-1) << '\n';
        }
        else
        {
            fin >> x;
            st = 0;
            dr = n+1;
            while (dr-st>1)
            {
                mij = (st+dr)/2;
                nr = query(mij);
                if (nr <= x)
                    st = mij;
                else dr=mij;
            }
            fout << st << '\n';
        }
    }
    return 0;
}

void update(int poz, int val)
{
    int i;

    for (i=poz;i<=n;i+=last2(i))
        AIB[i]+=val;
}

int query(int poz)
{
    int s=0, i;

    for (i=poz;i>=1;i-=last2(i))
        s+=AIB[i];
    return s;
}