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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 200005

struct Info{
	bool operator<(const struct Info &arg) const{
		return value < arg.value;
	}
	ll left,right,value;
};

struct Query{
	ll left,right,loc;
};

struct Data{
	bool operator<(const struct Data &arg) const{
		return loc < arg.loc;
	}
	ll loc,index;
};

ll uniformity[8*NUM],partial[8*NUM];
ll N = 1;
ll L[NUM],R[NUM],ans[NUM];
vector<ll> V;
map<ll,ll> MAP;
Info info[NUM];
Query query[NUM];
Data data[NUM]; //★二分探索をまとめて処理する際に使う★


void calc_size(ll first_N){
	while(N < first_N)N *= 2;
}

void init(){

	for(ll i = 0; i <= 2*N-2; i++){
		uniformity[i] = 0;
		partial[i] = 0;
	}
}

void add_and_updateNodes(ll left,ll right,ll value,ll node_id,ll node_left,ll node_right){

	if(right <= node_left || left >= node_right)return;
	else if(left <= node_left && right >= node_right){
		uniformity[node_id] += value;
	}else{
		partial[node_id] += (V[min(right,node_right)]-V[max(left,node_left)])*value;
		add_and_updateNodes(left,right,value,2*node_id+1,node_left,(node_left+node_right)/2);
		add_and_updateNodes(left,right,value,2*node_id+2,(node_left+node_right)/2,node_right);
	}
}

ll getSum(ll left,ll right,ll node_id,ll node_left,ll node_right){
	if(right <= node_left || left >= node_right)return 0;
	else if(left <= node_left && right >= node_right){
		return (V[node_right]-V[node_left])*uniformity[node_id]+partial[node_id];

	}else{
		ll sum = (V[min(right,node_right)]-V[max(left,node_left)])*uniformity[node_id];

		sum += getSum(left,right,2*node_id+1,node_left,(node_left+node_right)/2);
		sum += getSum(left,right,2*node_id+2,(node_left+node_right)/2,node_right);
		return sum;
	}
}

int main(){

	ll num_array,num_input,num_query;

	scanf("%lld %lld %lld",&num_array,&num_input,&num_query);

	V.push_back(-BIG_NUM); //注意★★
	V.push_back(BIG_NUM);

	for(int loop = 0; loop < num_input; loop++){

		scanf("%lld %lld %lld",&info[loop].left,&info[loop].right,&info[loop].value);
		info[loop].left--;

		V.push_back(info[loop].left);
		V.push_back(info[loop].right);
	}
	sort(info,info+num_input); //入力は昇順に行われたと解釈して問題なし

	for(int loop = 0; loop < num_query; loop++){

		scanf("%lld %lld %lld",&query[loop].left,&query[loop].right,&query[loop].loc);
		query[loop].left--;

		V.push_back(query[loop].left);
		V.push_back(query[loop].right);
	}

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

	//座標圧縮
	for(ll i = 0; i < V.size(); i++){

		MAP[V[i]] = i;
	}

	//セグ木のサイズを設定
	ll first_N = V.size();
	calc_size(first_N);

	int count;

	//二分探索の両端の初期値を設定
	for(int i = 0; i < num_query; i++){
		L[i] = 0;
		R[i] = num_input-1;
		ans[i] = 0;
	}

	int tmp_index;

	//★★二分探索をまとめて処理する★★
	while(true){

		init(); //セグ木を初期化

		count = 0;

		for(int i = 0; i < num_query; i++){

			if(L[i] > R[i])continue; //収束していたらSKIP

			data[count].loc = (L[i]+R[i])/2;
			data[count].index = i;
			count++;
		}

		if(count == 0)break;
		tmp_index = 0;

		sort(data,data+count);

		int k;

		for(int i = 0; i < num_input; i++){ //入力データをinfo[i].valueの昇順に見ていく

			add_and_updateNodes(MAP[info[i].left],MAP[info[i].right],1LL,0,0,N); //★★区間に1を足す(区間に足された数の個数を数えるため)★

			while(tmp_index < count && data[tmp_index].loc <= i){
				k = data[tmp_index].index;

				if(getSum(MAP[query[k].left],MAP[query[k].right],0,0,N) >= query[k].loc){

					ans[k] = info[data[tmp_index].loc].value; //なるべく小さく
					R[k] = data[tmp_index].loc-1;

				}else{

					L[k] = data[tmp_index].loc+1;
				}
				tmp_index++;
			}
		}
	}

	for(int i = 0; i < num_query; i++){

		printf("%lld\n",ans[i]);
	}

	return 0;
}