#include <cstdio>

#define lp2(x) (x&(x-1)^x)

using namespace std;

int aib[100005];
int n;

void update(int p, int val)
{
    for( ; p <= n ; p += lp2(p))
        aib[p] += val;
}

int query(int p)
{
    int S = 0;

    for( ; p ; p -= lp2(p))
        S += aib[p];

    return S;
}

int sh(int value)
{
    int st,dr,m;
    int q;
    st = 1;
    dr = n;
    while(st + 1 < dr)
    {
        m = (st + dr + 1) / 2;
        q = query(m);
        if(q >= value)
        {
            dr = m;
        }
        else
        {
            st = m;
        }
    }
    if(query(dr) == value)
        return dr;

    return st;
}

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

    int m;
    scanf("%d%d",&n,&m);

    int i;
    int tmp;
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%d",&tmp);
        update(i,tmp);
    }

    int op,a,b;
    for(i = 1 ; i <= m ; ++i)
    {
        scanf("%d",&op);

        switch(op)
        {
        case 0:
            {
                scanf("%d%d",&a,&b);
                update(a,b);
                break;
            }
        case  1:
            {
                scanf("%d%d",&a,&b);
                printf("%d\n",query(b) - query(a-1));
                break;
            }
        case 2:
            {
                scanf("%d%d",&a);
                printf("%d\n",sh(a));
            }
        }
    }

    return 0;
}