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<cstdio>
#include<utility>
#include<cassert>
#include<algorithm>

using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> PP;

const int B=1500;

struct Segtree{
	struct Node{
		int lch,rch;
		int val;
		long long all;
		Node(){
			lch=-1,rch=-1,val=0,all=0;
		}
	};
	Node nodes[B*80];
	int c;
	void init(){
		c=1;
		for(int i=0;i<B*80;i++) nodes[i]=Node();
	}
	void add(int l,int r,int k,int a,int b){
		if(l<=a&&b<=r){
			nodes[k].val++;
			nodes[k].all+=(b-a);
			return;
		}else if(r<=a||b<=l) return;
		if(nodes[k].lch==-1){
			nodes[k].lch=c++;
			nodes[k].rch=c++;
			assert(c<=B*80);
		}
		add(l,r,nodes[k].lch,a,(a+b)/2);
		add(l,r,nodes[k].rch,(a+b)/2,b);
		int le=max(l,a);
		int ri=min(r,b);
		nodes[k].all+=(ri-le);
	}
	void add(int l,int r){
		add(l,r,0,0,1001001001);
	}
	long long sum(int l,int r,int k,int a,int b){
		if(l<=a&&b<=r){
			return nodes[k].all;
		}else if(r<=a||b<=l) return 0;
		long long res=0;
		if(nodes[k].lch!=-1){
			res+=sum(l,r,nodes[k].lch,a,(a+b)/2);
			res+=sum(l,r,nodes[k].rch,(a+b)/2,b);
		}
		int le=max(a,l),ri=min(b,r);
		res+=(long long)nodes[k].val*(ri-le);
		return res;
	}
	long long sum(int l,int r){
		return sum(l,r,0,0,1001001001);
	}
};

Segtree segs[100100/B+1];

PP pps[100100];

int N,M,Q;

int main(){
	scanf("%d%d%d",&N,&M,&Q);
	for(int i=0;i<M;i++){
		int a,b,v;
		scanf("%d%d%d",&a,&b,&v);
		pps[i]=PP(v,P(a,b));
	}
	sort(pps,pps+M);
	for(int i=0;i<M/B;i++) segs[i].init();
	for(int i=0;i<M;i++){
		int a=pps[i].second.first;
		int b=pps[i].second.second;
		segs[i/B].add(a,b+1);
	}
	for(int q=0;q<Q;q++){
		int a,b;
		long long x;
		scanf("%d%d%lld",&a,&b,&x);
		long long sum=0;
		int id=0;
		for(id=0;id<M/B;id++){
		//	long long cur=val[id][b]-val[id][a-1];
			long long cur=segs[id].sum(a,b+1);
			if(sum+cur>=x) break;
			sum+=cur;
		}
		for(int i=id*B;;i++){
			int ca=pps[i].second.first,cb=pps[i].second.second;
			int le=max(ca,a),ri=min(cb,b);
			int ad=max(0,ri-le+1);
			sum+=ad;
			if(sum>=x){
				printf("%d\n",pps[i].first);
				break;
			}
		}
	}
	return 0;
}