#include <bits/stdc++.h>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

struct Aib {
    vector<int> aib;

    Aib(int n) : aib(n + 2) {
    }

    void add(int idx, int val) {
        while (idx < aib.size() - 1) {
            aib[idx] += val;
            idx += (idx & (-idx));
        }
    }

    int sum(int x) {
        int s = 0;
        while (x) {
            s += aib[x];
            x &= (x - 1);
        }
        return s;
    }
};

int cautbin(int val, Aib& a) {
    int st = 1, dr = a.aib.size() - 1;

    while (st < dr) {
        int mij = (st + dr) / 2;
        if (a.sum(mij) < val) {
            st = mij + 1;
        } else {
            dr = mij;
        }
    }
    return st;
}

int main() {
    int n, m, c, x, y;
    fin >> n >> m;
    Aib a(n);
    vector<int> val(n);
    for (int i = 1; i <= n; i++) {
        fin >> x;
        a.add(i, x);
        val[i - 1] = i;
    }
    for (int i = 0; i < m; i++) {
        fin >> c >> x;
        if (c == 0) {
            fin >> y;
            a.add(x, y);
        } else if (c == 1) {
            fin >> y;
            fout << a.sum(y) - a.sum(x - 1) << "\n";
        } else {
            fout << cautbin(x, a) << "\n";
        }
    }
}