Problem: I - The J-th Number

Problem Statement

You are given N empty arrays, t_1, ..., t_n. At first, you execute M queries as follows.

* add a value v to array t_i (a \leq i \leq b)



Next, you process Q following output queries.

* output the j-th number of the sequence sorted all values in t_i (x \leq i \leq y)



Input

The dataset is formatted as follows.


N M Q
a_1 b_1 v_1
...
a_M b_M v_M
x_1 y_1 j_1
...
x_Q y_Q j_Q


The first line contains three integers N (1 \leq N \leq 10^9), M (1 \leq M \leq 10^5) and Q (1 \leq Q \leq 10^5). Each of the following M lines consists of three integers a_i, b_i and v_i (1 \leq a_i \leq b_i \leq N, 1 \leq v_i \leq 10^9). Finally the following Q lines give the list of output queries, each of these lines consists of three integers x_i, y_i and j_i (1 \leq x_i \leq y_i \leq N, 1 \leq j_i \leq Σ_{x_i \leq k \leq y_i} |t_k|).

Output

For each output query, print in a line the j-th number.

Sample Input 1


5 4 1
1 5 1
1 1 3
4 5 1
3 4 2
1 3 4


Output for the Sample Input 1


2


After the M-th query is executed, each t_i is as follows:


[1,3], [1], [1,2], [1,1,2], [1,1]


The sequence sorted values in t_1, t_2 and t_3 is [1,1,1,2,3]. In the sequence, the 4-th number is 2.

Sample Input 2


10 4 4
1 4 11
2 3 22
6 9 33
8 9 44
1 1 1
4 5 1
4 6 2
1 10 12


Output for the Sample Input 2


11
11
33
44






Example

Input

5 4 1
1 5 1
1 1 3
4 5 1
3 4 2
1 3 4


Output

2

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

struct Node {
    using NP = const Node*;

    ll sm, now;
    ll dsm;
    /*
     init_leaf, update, push
    */
    void init_leaf(ll d) {
        sm = now = 0;
        dsm = d;
    }
    void update() {
        dsm = l->dsm + r->dsm;
        sm = l->sm + r->sm + now * dsm;
    }
    void lzdata(ll x) {
        sm += dsm * x;
        now += x;
    }
    void push() {
    }
    /// push???const?????¢?????????????????§??????
    void push() const {
        const_cast<Node*>(this)->push();
    }


    NP add(int a, int b) const {
        if (b <= 0 or sz <= a) return this;
        if (a <= 0 and sz <= b) {
            auto n = make(this);
            n->lzdata(1);
            return n;
        }
        push();
        int u = sm;
        auto nl = l->add(a, b);
        auto nr = r->add(a - sz/2, b - sz/2);
        auto n = make(this);
        n->l = nl;
        n->r = nr;
        n->update();
        return n;
    }
    ll get(int a, int b, ll cur = 0) const {
        if (b <= 0 or sz <= a) return 0;
        if (a <= 0 and sz <= b) {
            return sm + cur * dsm;
        }
        push();
        return l->get(a, b, cur + now) + r->get(a-sz/2, b-sz/2, cur + now);
    }

    NP l, r;
    int sz;
    Node() {}
    Node(int sz, ll d[]) : sz(sz), now(0) {
        if (sz == 1) {
            init_leaf(d[0]);
            return;
        }
        l = new Node(sz/2, d);
        r = new Node(sz - sz/2, d+sz/2);
        update();
    }
    static Node* make(NP x) {
        auto n = new Node();
        *n = *x;
        return n;
    }
};


int main() {
    int n, m, q;
    cin >> n >> m >> q;
    const int MM = 100100;
    const int MQ = 100100;
    const int MX = (MM+MQ)*2;
    const int MY = MM;
    static int a[MM], b[MM], v[MM];
    static vector<int> g[MY];
    static int x[MQ], y[MQ];
    static ll j[MQ];
    vector<int> vl, xl;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> v[i]; b[i]++;
        vl.push_back(v[i]);
        xl.push_back(a[i]);
        xl.push_back(b[i]);
    }
    for (int i = 0; i < q; i++) {
        cin >> x[i] >> y[i] >> j[i]; y[i]++;
        xl.push_back(x[i]);
        xl.push_back(y[i]);
    }
    sort(vl.begin(), vl.end());
    vl.erase(unique(vl.begin(), vl.end()), vl.end());

    for (int i = 0; i < m; i++) {
        v[i] = lower_bound(vl.begin(), vl.end(), v[i]) - vl.begin();
        g[v[i]].push_back(i);
    }

    sort(xl.begin(), xl.end());
    xl.erase(unique(xl.begin(), xl.end()), xl.end());

    auto x2xl = [&](const int &x) {
        return lower_bound(xl.begin(), xl.end(), x) - xl.begin();
    };

    for (int i = 0; i < m; i++) {
        a[i] = x2xl(a[i]);
        b[i] = x2xl(b[i]);
    }
    for (int i = 0; i < q; i++) {
        x[i] = x2xl(x[i]);
        y[i] = x2xl(y[i]);
    }

    // for (int i = 0; i < m; i++) {
    //     printf("%d %d %d\n", a[i], b[i], v[i]);
    // }
    // for (int i = 0; i < q; i++) {
    //     printf("%d %d %lld\n", x[i], y[i], j[i]);
    // }
    static ll deg[MX];
    for (int i = 0; i < (int)xl.size() - 1; i++) {
        deg[i] = xl[i+1] - xl[i];
    }
    static const Node* tr[MY];
    tr[0] = new Node(MX, deg);
    for (int i = 1; i < MY; i++) {
        tr[i] = tr[i-1];
        for (int d: g[i-1]) {
            tr[i] = tr[i]->add(a[d], b[d]);
        }

    }
    for (int i = 0; i < q; i++) {
        int l = 0, r = MY-1;
        while (r-l > 1) {
            int md = (l+r)/2;
            if (tr[md]->get(x[i], y[i]) < j[i]) {
                l = md;
            } else {
                r = md;
            }
        }
//        printf("%d %d\n", l, r);
        cout << vl[l] << endl;
    }
    return 0;
}