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<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct wolf{
	vector<pair<int,int> >A;
	vector<pair<int,long long> >B;
	int left;
	int right;
	wolf(){
		left=right=-1;
	}
};
wolf pool[3500000];
int sz=0;
void add(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return ;
	if(c<=a&&b<=d){
		pool[e].A.push_back(make_pair(f,1));
		return;
	}
	//printf("%d: %d %d\n",e,a,b);
	int num=min(b,d)-max(a,c)+1;
	pool[e].B.push_back(make_pair(f,num));
	int to;
	if(min((a+b)/2,d)>=max(a,c)){
		to=pool[e].left;
		if(!~to){
			to=pool[e].left=sz++;
		}
		add(a,(a+b)/2,c,d,to,f);
	}
	if(min(b,d)>=max((a+b)/2+1,c)){
		to=pool[e].right;
		if(!~to){
			to=pool[e].right=sz++;
		}
		add((a+b)/2+1,b,c,d,to,f);
	}
}
long long cnt(int a,int b,int c,int d,int e,int f){
//	printf("%d %d %d %d %d %d\n",a,b,c,d,e,f);
	if(d<a||b<c)return 0LL;
	if(c<=a&&b<=d){
		long long ret=(*(lower_bound(pool[e].B.begin(),pool[e].B.end(),make_pair(f+1,0LL))-1)).second;
		int num=b-a+1;
		ret+=(long long)((*(lower_bound(pool[e].A.begin(),pool[e].A.end(),make_pair(f+1,0))-1)).second)*num;
		return ret;
	}
	int num=min(b,d)-max(a,c)+1;
	long long ret=(long long)((*(lower_bound(pool[e].A.begin(),pool[e].A.end(),make_pair(f+1,0))-1)).second)*num;
	int to=pool[e].left;
	if(~to){
		ret+=cnt(a,(a+b)/2,c,d,to,f);
	}
	to=pool[e].right;
	if(~to){
		ret+=cnt((a+b)/2+1,b,c,d,to,f);
	}
	return ret;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	sz++;
	for(int i=0;i<b;i++){
		int p,q,r;
		scanf("%d%d%d",&p,&q,&r);
		p--;q--;
		add(0,(1<<30)-1,p,q,0,r);
	}
	for(int i=0;i<sz;i++){
	//	printf("%d: %d %d\n",i,pool[i].A.size(),pool[i].B.size());
		pool[i].A.push_back(make_pair(0,0));
		pool[i].B.push_back(make_pair(0,0));
		
		std::sort(pool[i].A.begin(),pool[i].A.end());
		long long now=0;
		for(int j=0;j<pool[i].A.size();j++){
		//	if(j)printf("%d: %d %d\n",i,pool[i].A[j].first,pool[i].A[j].second);
			now+=pool[i].A[j].second;
			pool[i].A[j].second=now;
		}
		std::sort(pool[i].B.begin(),pool[i].B.end());
		now=0;
		for(int j=0;j<pool[i].B.size();j++){
	//		if(j)printf("%d: %d %d\n",i,pool[i].B[j].first,pool[i].B[j].second);
			now+=pool[i].B[j].second;
			pool[i].B[j].second=now;
		}
	}
	for(int i=0;i<c;i++){
		int p,q;
		long long r;
		scanf("%d%d%lld",&p,&q,&r);
		p--;q--;
		int left=0;
		int right=1000000007;
		while(left+1<right){
			int M=(left+right)/2;
			long long val=cnt(0,(1<<30)-1,p,q,0,M);
		//	printf("%lld\n",val);
			if(val>=r)right=M;
			else left=M;
		}
		printf("%d\n",right);
	}
}