#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 st = 1, dr = n, mi;
        while (st < dr){
            mi=(st+dr)/2;
            y = sm(mi);
            if(y < x)
                st =mi+1;
            else dr =mi;
        }
        g << dr << '\n';
    }
    return 0;
}