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

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

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

long long dist(long long val) {
    return val & -val;
}

void add(long long val, int pos) {
    while (pos <= n) {
        v[pos] += val;
        pos += dist(pos);
    }
}

long long q1(int pos) {
    long long s = 0;
    while (pos > 0) {
        s += v[pos];
        pos -= dist(pos);
    }
    return s;
}

int main() {

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

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

    fout.close();
    return 0;
}