// k = (x^(x-1)) & x
#include <cstdio>

#define step(k) ((k ^ (k-1) ) & k)
#define MAX_N 100005

int poz, val;
int N, M, V[MAX_N], A[MAX_N];

void update(int poz, int val)
{
    while(poz <= N)
    {
        A[poz] += val;
        poz += step(poz);
    }
}

int sum(int poz)
{
    int R = 0;
    while(poz)
    {
        R += A[poz];
        poz -= step(poz);
    }
    return R;
}

int querry(int k)
{
    int pas, i;
    for(pas = 1; pas < N; pas <<= 1);

    for(i = 0; pas > 0; pas >>= 1)
        if(i + pas <= N)
            if(k >= A[i + pas])
            {
                k -= A[i + pas], i += pas;
                if(k == 0)
                    return i;
            }
    return -1;
}

void solve()
{
    int t,a,b;
    while(M--)
    {
        scanf("%d",&t);

        if(t == 0)
        {
            scanf("%d %d",&a, &b);
            val = b;
            poz = a;
            update(a,b);
        }

        if(t == 1)
        {
            scanf("%d %d",&a, &b);
            printf("%d\n", sum(b) - sum(a-1));
        }

        if(t == 2)
        {
            scanf("%d",&a);
            printf("%d\n", querry(a));
        }
    }
}

void citire()
{
    scanf("%d %d",&N,&M);
    for(int i = 1; i <= N; ++i)
    {
        scanf("%d ",V+i);
        update(i,V[i]);
    }
}

int main()
{
    freopen("aib.in","rt",stdin);
    freopen("aib.out","wt",stdout);
    citire();
    solve();
}