#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

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

const int MAXN = 100005;
int n, m;
int v[MAXN];

int lsb(int k) {
    return k & (-k);
}

void add(int k, int p) {
    while (p <= n) {
        v[p] += k;
        p += lsb(p);
    }
}

int query(int p) {
    int s = 0;
    while (p >= 1) {
        s += v[p];
        p -= lsb(p);
    }
    return s;
}

int main() {

    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int k;
        fin >> k;
        add(k, i);
    }

    for (int i = 1; i <= m; ++i) {
        int k;
        fin >> k;
        if (k == 0) {
            int a, b;
            fin >> a >> b;
            add(b, a);
        }
        else if (k == 1) {
            int a, b;
            fin >> a >> b;
            fout << query(b) - query(a - 1) << '\n';
        }
        else {
            int a;
            fin >> a;
            int st = 1;
            int dr = n;
            int sol = 0;
            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (query(mid) >= a) {
                    dr = mid - 1;
                }
                else if (query(mid) <= a) {
                    st = mid + 1;
                }
                if (query(mid) == a) {
                    sol = mid;
                }
            }
            fout << sol << '\n';
        }
    }

    fout.close();
    return 0;
}