#include <fstream>
#include <iostream>
#define zeros(x) ((x^(x-1))&x)

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int n, m, i, j, arb[100005];
int x, y,q;

void update(int poz, int val) {
    for (; poz <= n; poz += zeros(poz))
        arb[poz] += val;
}

int sm(int poz) {
    int s =0;
    while (poz>0) {
        s+= arb[poz];
        poz -= zeros(poz);
    }
    return s;
}

int main() {
    f >> n >> m;
    for (i = 1; i <= n; i++) {
        f >> x;
        update(i,x);
    }
    while (m--) {
        f >> q >> x;
        if (q<2) {
            f >> y;
            if (q==0)
                update(x,y);
            else g << sm(y) - sm(x-1)<<'\n';
            continue;
        }
        int p = 1, i;
        while (p < n) p *= 2;
        while (p) {
            if (j+p<=n){
                y = sm(j+p);
                if (y <= x)
                    j += p;
                if (y == x)
                    break;
            }
            p /= 2;
        }
        g << j << '\n';
    }
    return 0;
}