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 <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#pragma warning(disable : 4996)
using namespace std;
int N, M, Q, a[100009], b[100009], v[100009], p[100009], x[100009], y[100009], ans[100009]; long long z[100009], ss[400009], offset[100009][333];
int cqx[100009], cqy[100009], cvx[100009], cvy[100009], cs[400009], as[400009];
int main() {
	scanf("%d %d %d", &N, &M, &Q);
	vector<int> cp(2 * (M + Q));
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &a[i], &b[i], &v[i]), p[i] = i;
		cp[i * 2] = --a[i];
		cp[i * 2 + 1] = b[i];
	}
	for (int i = 0; i < Q; i++) {
		scanf("%d %d %lld", &x[i], &y[i], &z[i]), z[i]--, ans[i] = -1;
		cp[(i + M) * 2] = --x[i];
		cp[(i + M) * 2 + 1] = y[i];
	}
	sort(cp.begin(), cp.end());
	cp.erase(unique(cp.begin(), cp.end()), cp.end());
	sort(p, p + M, [](int i, int j) { return v[i] < v[j]; });
	for (int i = 0; i < Q; i++) {
		cqx[i] = lower_bound(cp.begin(), cp.end(), x[i]) - cp.begin();
		cqy[i] = lower_bound(cp.begin(), cp.end(), y[i]) - cp.begin();
	}
	int C = cp.size() - 1, B = sqrt(M);
	for (int i = 0; i < B; i++) {
		int pl = i * M / B, pr = (i + 1) * M / B;
		for (int j = pl; j < pr; j++) {
			as[lower_bound(cp.begin(), cp.end(), a[p[j]]) - cp.begin()]++;
			as[lower_bound(cp.begin(), cp.end(), b[p[j]]) - cp.begin()]--;
		}
		cs[0] = as[0];
		for (int j = 0; j < C; j++) cs[j + 1] = cs[j] + as[j + 1];
		for (int j = 0; j < C; j++) ss[j + 1] = ss[j] + 1LL * cs[j] * (cp[j + 1] - cp[j]);
		for (int j = 0; j < Q; j++) offset[j][i + 1] = ss[cqy[j]] - ss[cqx[j]];
	}
	for (int i = 0; i < B; i++) {
		int pl = i * M / B, pr = (i + 1) * M / B;
		vector<int> scp(2 * (pr - pl) + 2); scp[1] = N;
		for (int j = pl; j < pr; j++) {
			scp[(j - pl) * 2 + 2] = a[p[j]];
			scp[(j - pl) * 2 + 3] = b[p[j]];
		}
		sort(scp.begin(), scp.end());
		scp.erase(unique(scp.begin(), scp.end()), scp.end());
		int sc = scp.size() - 1;
		fill(cs, cs + sc + 1, 0);
		vector<int> vs;
		for (int j = 0; j < Q; j++) {
			if (offset[j][i] <= z[j] && z[j] < offset[j][i + 1]) {
				vs.push_back(j);
			}
		}
		int vc = vs.size();
		for (int j = 0; j < vc; j++) {
			cvx[j] = lower_bound(scp.begin(), scp.end(), x[vs[j]] + 1) - scp.begin() - 1;
			cvy[j] = lower_bound(scp.begin(), scp.end(), y[vs[j]] + 1) - scp.begin() - 1;
		}
		for (int j = pl; j < pr; j++) {
			int ptl = lower_bound(scp.begin(), scp.end(), a[p[j]]) - scp.begin();
			int ptr = lower_bound(scp.begin(), scp.end(), b[p[j]]) - scp.begin();
			for (int k = ptl; k < ptr; k++) cs[k]++;
			for (int k = 0; k < sc; k++) ss[k + 1] = ss[k] + 1LL * cs[k] * (scp[k + 1] - scp[k]);
			for (int k = 0; k < vc; k++) {
				long long val = 1LL * cs[cvx[k]] * (scp[cvx[k] + 1] - x[vs[k]]) + 1LL * cs[cvy[k]] * (y[vs[k]] - scp[cvy[k]]) + ss[cvy[k]] - ss[cvx[k] + 1];
				if (cvx[k] == cvy[k]) val = 1LL * cs[cvx[k]] * (y[vs[k]] - x[vs[k]]);
				if (val + offset[vs[k]][i] > z[vs[k]] && ans[vs[k]] == -1) ans[vs[k]] = v[p[j]];
			}
		}
	}
	for (int i = 0; i < Q; i++) printf("%d\n", ans[i]);
	return 0;
}