Problem: Write a program which manipulates a sequence A = {a0, a1, . . . , an−1} with the following operations:

* update(s, t, x): change as, as+1, ..., at to x.
* find(i): output the value of ai.



Note that the initial values of ai (i = 0, 1, . . . , n−1) are 231-1.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* 0 ≤ s ≤ t < n
* 0 ≤ i < n
* 0 ≤ x < 231−1

Input


n q
query1
query2
:
queryq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi is given in the following format:


0 s t x


or


1 i


The first digit represents the type of the query. '0' denotes update(s, t, x) and '1' denotes find(i).

Output

For each find operation, print the value.

Examples

Input

3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0
1 1


Output

1
3


Input

1 3
1 0
0 0 0 5
1 0


Output

2147483647
5

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <functional>
#include <limits>

template <class Data, class Operator>
class CoSegmentTree {
    using OperatorMerger = std::function<Operator(Operator, Operator)>;
    using Applier = std::function<Data(Data, Operator)>;

public:
    int length;
    std::vector<Operator> ope;
    Data dat_id;
    Operator ope_id;
    OperatorMerger opem;
    Applier app;

    explicit CoSegmentTree(int N, Data dat_id, Operator ope_id, OperatorMerger opem, Applier app)
        : length(1), dat_id(dat_id), ope_id(ope_id), opem(opem), app(app) {
        while (length < N) length *= 2;
        ope.assign(length * 2, ope_id);
    }

    // half-open interval [ql, qr)
    void update(int ql, int qr, Operator e) { return update(ql, qr, e, 1, 0, length); }

    void update(int ql, int qr, Operator e, int nidx, int nl, int nr) {
        if (nr <= ql || qr <= nl) return;
        if (ql <= nl && nr <= qr) {
            ope[nidx] = opem(ope[nidx], e);
            return;
        }
        // 子に作用素を伝播
        ope[nidx * 2] = opem(ope[nidx * 2], ope[nidx]);
        ope[nidx * 2 + 1] = opem(ope[nidx * 2 + 1], ope[nidx]);
        ope[nidx] = ope_id;
        // 子を再帰的に更新
        update(ql, qr, e, nidx * 2, nl, (nl + nr) / 2);
        update(ql, qr, e, nidx * 2 + 1, (nl + nr) / 2, nr);
    }

    Data query(int idx) {
        int nidx = idx + length;
        Data ret = app(dat_id, ope[nidx]);
        while (nidx > 0) {
            nidx /= 2;
            ret = app(ret, ope[nidx]);
        }
        return ret;
    }
};

const int INF = std::numeric_limits<int>::max();

int main() {
    int N, Q;
    std::cin >> N >> Q;

    CoSegmentTree<int, int> seg(N, INF, INF,
                                [](int a, int b) { return (b == INF ? a : b); },
                                [](int a, int e) { return (e == INF ? a : e); });

    for (int q = 0; q < Q; ++q) {
        int k;
        std::cin >> k;
        if (k == 0) {
            int l, r, x;
            std::cin >> l >> r >> x;
            seg.update(l, r + 1, x);
        } else {
            int i;
            std::cin >> i;
            std::cout << seg.query(i) << std::endl;
        }
    }
    return 0;
}