#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100003;

int n, q;
int t[NMAX];

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

void add(int x, int y) {
    for(int i = x; i <= n; i += lsb(i)) {
        t[i] += y;
    }
}

int sum(int x) {
    int ans = 0;
    for(int i = x; i >= 1; i -= lsb(i)) {
        ans += t[i];
    }
    return ans;
}

int main() {
    in >> n >> q;
    for(int i = 1; i <= n; i++) {
        int x;
        in >> x;
        add(i, x);
    }
    while(q--) {
        int type;
        in >> type;
        if(type == 0) {
            int a, b;
            in >> a >> b;
            add(a, b);
        } else if(type == 1) {
            int a, b;
            in >> a >> b;
            out << sum(b) - sum(a-1) << '\n';
        } else {
            int a;
            in >> a;
            int l = 1, r = n, last = -1;
            while(r - l >= 0) {
                int mid = (l + r) >> 1, s = sum(mid);
                if(s >= a) {
                    last = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            out << last << '\n';
        }
    }
    return 0;
}