#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

#define INF ( (1 << 30) - 1 + (1 << 30) )
#define mod 666013
#define lsb(x) ( x & (-x) )

using namespace std;

int n, m, i, x, y, op;
int aib[100005];

void U(int poz, int val)
{
    int i;
    for(i = poz; i <= n; i += lsb(i))
        aib[i] += val;
}

int Q(int poz)
{
    int s = 0, i;
    for(i = poz; i > 0; i -= lsb(i))
        s += aib[i];
    return s;
}

int S(int sum)
{
    int i = 0;
    int r = 0;
    int s = 0;
    for(i = 20; i >= 0; i--)
    {
        if( (1 << i) + r > n )
            continue;
        int p = (1 << i);
        if(s + aib[r + p] <= sum)
        {
            r += p;
            s += aib[p];
        }
    }
    return r;
}

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

    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        U(i, x);
    }
    while(m--)
    {
        scanf("%d", &op);
        if(op == 0)
        {
            scanf("%d%d", &x, &y);
            U(x, y);
        }
        else if(op == 1)
        {
            scanf("%d%d", &x, &y);
            printf("%d\n", Q(y) - Q(x - 1));
        }
        else
        {
            scanf("%d", &x);
            printf("%d\n", S(x));
        }
    }
    return 0;
}