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;



#define int long long
struct NODE{
	vector<pair<int,int>> seg;
	vector<int> special;
	bool sorted;
	NODE *l,*r;
	NODE(){
		l = r = NULL;
		sorted = false;
	}
};

#define N_MAX (1073741824ll)
NODE* add(int l,int r,int v,NODE *root,int a=1,int b=N_MAX){
	if( r < a || b < l ) return root;
	if( root == NULL ) root = new NODE();
	if( l <= a && b <= r ){
		root->special.push_back(v);
		return root;
	}else{
		root->seg.push_back({v,min(r,b)-max(l,a)+1});
		int m = (a+b)/2;
		
		root->l = add(l,r,v,root->l,a,m);
		root->r = add(l,r,v,root->r,m+1,b);
	}
	return root;
}
void init(NODE *root){
	if( root == NULL ) return;
	sort(root->seg.begin(),root->seg.end());
	sort(root->special.begin(),root->special.end());
	for(int i = 1 ; i < root->seg.size() ; i++){
		root->seg[i].second += root->seg[i-1].second;
	}
	init(root->l);
	init(root->r);
	return;
}

int get(int l,int r,int v,NODE *root,int a=1,int b=N_MAX){
	if( r < a || b < l ) return 0;
	if( root == NULL ) return 0;
	int ans = 0;
	ans += (min(r,b)-max(l,a)+1) * (upper_bound(root->special.begin(),root->special.end(),v)-root->special.begin());
	if( l <= a && b <= r ){
		int idx = upper_bound(root->seg.begin(),root->seg.end(),make_pair(v+1,-1ll)) - root->seg.begin() - 1;
		if( idx >= 0 ){
			ans += root->seg[idx].second;
		}
	}else{
		int m = (a+b)/2;
		ans += get(l,r,v,root->l,a,m);
		ans += get(l,r,v,root->r,m+1,b);
	}
	return ans;
}


signed main(){
	NODE *root = new NODE();
	int N,M,Q;
	cin >> N >> M >> Q;
	vector<int> val;
	while(M--){
		int a,b,v;
		scanf("%lld%lld%lld",&a,&b,&v);
		add(a,b,v,root);
		val.push_back(v);
	}
	init(root);
	// for( auto &it : seg ){
		// sort(it.second.begin(),it.second.end());
		// for(int i = 1 ; i < it.second.size() ; i++){
			// it.second[i].second += it.second[i-1].second;
		// }
	// }
	// for( auto &it : special ){
		// sort(it.second.begin(),it.second.end());
	// }
	//cout << get(1,1000,1,root) << endl;
	sort(val.begin(),val.end());
	val.erase(unique(val.begin(),val.end()),val.end());
	while(Q--){
		int a,b,j;
		scanf("%lld%lld%lld",&a,&b,&j);
		int l = 0 , r = val.size()-1;
		while( l != r ){
			int m = (l+r)/2;
			if( get(a,b,val[m],root) < j ){
				l = m+1;
			}else{
				r = m;
			}
		}
		printf("%lld\n",val[l]);
	}
}