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 <bits/stdc++.h>
using namespace std;
using ll = long long;
const int PMAX = 10000000;

template <typename T>
struct node {
	T val, add;
	node *l, *r;
	node() {}
	node(T val, T add) : val(val), add(add), l(nullptr), r(nullptr) {}
	void init(T v, T a, node *left, node *right) {
		val = v;
		add = a;
		l = left;
		r = right;
	}
};

node<ll> pool[PMAX];

template <typename T>
class SaikyoSegmentTree {
	const ll n;
	const T id;
	int it, rit;
	vector<node<T>*> root;
	T getval(node<T> *x) {
		return x == nullptr ? id : x->val;
	}
	T getadd(node<T> *x) {
		return x == nullptr ? id : x->add;
	}
	node<T>* getl(node<T> *x) {
		return x == nullptr ? nullptr : x->l;
	}
	node<T>* getr(node<T> *x) {
		return x == nullptr ? nullptr : x->r;
	}
	ll size(ll n) {
		assert(n < (1ll << 62ll));
		ll res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	node<T> *new_node(T val, T add, node<T> *l = nullptr, node<T> *r = nullptr) {
		pool[it].init(val, add, l, r);
		return &pool[it++];
	}
	node<T> *fix(node<T> *x, ll l, ll r, T val, ll lb, ll ub) {
		if (r <= lb || ub <= l) return x;
		if (l <= lb && ub <= r) return new_node(getval(x), getadd(x) + val, getl(x), getr(x));
		ll c = (lb + ub) / 2;
		auto nl = fix(getl(x), l, r, val, lb, c);
		auto nr = fix(getr(x), l, r, val, c, ub);
		return new_node(getval(x) + val * (min(r, ub) - max(l, lb)), getadd(x), nl, nr);
	}
	T sub(node<T> *x, ll l, ll r, ll lb, ll ub) {
		if (x == nullptr) return id;
		if (ub <= l || r <= lb) return id;
		if (l <= lb && ub <= r) return x->val + x->add * (ub - lb);
		ll c = (lb + ub) / 2;
		return sub(getl(x), l, r, lb, c) + sub(getr(x), l, r, c, ub) + x->add * (min(r, ub) - max(l, lb));
	}
public:
	SaikyoSegmentTree(ll n_, T id_) : n(size(n_)), id(id_), it(0) {
		root.push_back(nullptr);
	}
	void add(ll l, ll r, T val, int rt = -1) {
		if (rt == -1) rt = root.size() - 1;
		assert(0 <= rt && rt < (int)root.size());
		root.push_back(fix(root[rt], l, r + 1, val, 0, n));
	}
	T find(ll l, ll r, int rt = -1) {
		if (rt == -1) rt = root.size() - 1;
		assert(0 <= rt && rt < (int)root.size());
		return sub(root[rt], l, r + 1, 0, n);
	}
};

int main()
{
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll N, M, Q;
	cin >> N >> M >> Q;
	vector<tuple<int, int, int>> vab(M);
	for (int i = 0; i < M; i++) {
		cin >> get<1>(vab[i]) >> get<2>(vab[i]) >> get<0>(vab[i]); get<1>(vab[i])--; get<2>(vab[i])--;
	}
	sort(vab.begin(), vab.end());
	SaikyoSegmentTree<ll> sst(N, 0);
	for (int i = 0; i < M; i++) {
		sst.add(get<1>(vab[i]), get<2>(vab[i]), 1);
	}
	ll x, y, j;
	while (Q--) {
		cin >> x >> y >> j; x--; y--;
		ll l = 0, r = M;
		while(l + 1 < r) {
			ll c = (l + r) / 2;
			if (sst.find(x, y, c) >= j) {
				r = c;
			}
			else {
				l = c;
			}
		}
		printf("%d\n", get<0>(vab[r - 1]));
	}
	return 0;
}