#include <fstream>
#include <vector>


class BinaryIndexTree {
public:

    BinaryIndexTree(int N): tree_(N, 0) {

    }

    BinaryIndexTree(const std::vector<int>& v): BinaryIndexTree(v.size()) {
        for (int i = 0; i < v.size(); ++i) {
            update(i + 1, v[i]);
        }
    } 

    void update(int pos, int val) {
        for (; pos <= tree_.size(); pos += (pos & -pos)) {
            tree_[pos - 1] +=  val;
        }
    }

    int cumulitiveSum(int pos) const {
        int sum = 0;
        for (; pos; pos -= (pos & -pos)) {
            sum += tree_[pos - 1];
        }
        return sum;
    }

    int at(int pos) const { 
        int sum = tree_[pos - 1];
        int stopIdx = pos - (pos & -pos);
        for (--pos; pos != stopIdx; pos -= pos & -pos) {
            sum -= tree_[pos - 1];
        }
        return sum;
    }

    int findPos(int cumFreq) const {
        int idx = 0;
        int bitMask = 0;
        for (int N = tree_.size(); N; N >>= 1) ++bitMask;
        for (bitMask = 1 << bitMask; bitMask != 0; bitMask >>= 1) {
            int tIdx = idx + bitMask;
            if (tIdx > tree_.size()) continue;
            if (cumFreq == tree_[tIdx - 1]) {
                return tIdx;
            }
            if (cumFreq > tree_[tIdx - 1]) {
                idx = tIdx;
                cumFreq -= tree_[tIdx - 1];
            }
        }
        if (cumFreq != 0) {
            return -1;
        }
        return idx;
    }



private:
    std::vector<int> tree_;

};

int main() {
    std::ifstream in {"aib.in"};
    std::ofstream out {"aib.out"};

    int N, M;
    std::vector<int> v;

    in >> N >> M;
    v.resize(N);
    for (int i = 0; i < N; ++i) {
        in >> v[i];
    }

    BinaryIndexTree tree{v};
    int op, a, b;
    for (int i = 0; i < M; ++i) {
        in >> op >> a;
        if (op == 2) {
            out << tree.findPos(a) << '\n';
        } else {
            in >> b;
            if (op == 1) {
                out << (tree.cumulitiveSum(b) - tree.cumulitiveSum(a - 1)) << '\n';
            } else {
                tree.update(a, b);
            }
        }
    }

    return 0;
}