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 <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <unordered_map>
#include <iterator>
#include <functional>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;

template<typename Handler, int RESERVE = (1<<29)>
struct SegTreeDynamicLazy{
	typedef typename Handler::val_t val_t;
	typedef typename Handler::opr_t opr_t;
	Handler hdl;
	struct Node{
		static Node *pool;
		static int ptr;
		static int New(const Node *v){
			if(!pool) pool = (Node*)malloc(RESERVE);
			pool[++ptr] = v ? *v : Node();
			return ptr;
		}
		static void allClear(){
			ptr = 0;
		}
		int lch, rch;
		val_t val;
		opr_t lazy;
		Node(Node *v=0):val(Handler::def_val()), lazy(Handler::def_lazy()){
			if(v){
				(*this) = *v;
			}else lch = rch = 0;
		}
	};
	int root;
	ll n;
	Node *p;
	
	SegTreeDynamicLazy(ll size):hdl(),n(size){
		root = Node::New(0);
		p = Node::pool;
	}
	
	
	int push(int v, ll l, ll r, const int &pers=0){
		if(p[v].lazy == hdl.def_lazy()) return v;
		opr_t lz = p[v].lazy;
		p[v].lazy = hdl.def_lazy();
		if(r-l<=1) return v;
		if(pers || !p[v].lch) p[v].lch = Node::New(&p[p[v].lch]);
		if(pers || !p[v].rch) p[v].rch = Node::New(&p[p[v].rch]);
		p[p[v].lch].lazy = hdl.push(p[p[v].lch].lazy, lz);
		p[p[v].rch].lazy = hdl.push(p[p[v].rch].lazy, lz);
		p[p[v].lch].val = hdl.resolve(p[p[v].lch].val, lz, l, (l+r)/2);
		p[p[v].rch].val = hdl.resolve(p[p[v].rch].val, lz, (l+r)/2, r);
		return v;
	}
	int update(ll a,ll b,const opr_t &x, int v,ll l,ll r, const int &pers){
		if(r<=a||b<=l) return v;
		if(pers || !v) v = Node::New(&p[v]);
		if(a<=l&&r<=b){
			p[v].lazy = hdl.push(p[v].lazy, x);
			p[v].val = hdl.resolve(p[v].val, x, l, r);
			return v;
		}
		push(v, l, r, pers);
		p[v].lch = update(a, b, x, p[v].lch, l, (l+r)/2, pers);
		p[v].rch = update(a, b, x, p[v].rch, (l+r)/2, r, pers);
		p[v].val = hdl.merge(p[v].lch ? p[p[v].lch].val : hdl.def_val(), p[v].rch ? p[p[v].rch].val : hdl.def_val());
		return v;
	}
	val_t query(ll a,ll b,int v,ll l,ll r, opr_t lazy){
		if(r<=a||b<=l) return hdl.def_val();
		if(!v) return hdl.resolve(hdl.def_val(), lazy, max(l, a), min(r, b));
		if(a<=l&&r<=b) return hdl.resolve(p[v].val, lazy, l, r);
		lazy = hdl.push(p[v].lazy, lazy);
		return hdl.merge(query(a, b, p[v].lch, l, (l+r)/2, lazy), 
						 query(a, b, p[v].rch, (l+r)/2, r, lazy));
	}
	int update(ll a, ll b, opr_t x, int r = 0, int pers=0){return update(a, b, x, r?r:root, 0, n, pers);}
	val_t query(ll a, ll b, int r = 0){	return query(a, b, r?r:root, 0, n, hdl.def_lazy());}
	val_t operator[](size_t i){return query(i, i+1);}
	friend ostream& operator<<(ostream &os, SegTreeDynamicLazy<Handler> &t){
		REP(i, t.n) os << (i ? ", " : "[") << "(" << i << ")" << t.query(i, i+1);
		return os << "]";
	}
};
template<class H, int R> typename SegTreeDynamicLazy<H, R>::Node* SegTreeDynamicLazy<H, R>::Node::pool;
template<class H, int R> int SegTreeDynamicLazy<H, R>::Node::ptr;

struct handler{
	typedef ll val_t;
	typedef int opr_t;
	handler(){}
	static val_t def_val(){ return 0; }
	static opr_t def_lazy(){ return 0; }
	static val_t resolve(const val_t &x, const opr_t &y, ll l, ll r){
		return x + (ll)y*(r-l);
	}
	static opr_t push(const opr_t &x, const opr_t &y){
		return x + y;
	}
	static val_t merge(const val_t &x, const val_t &y){
		return x + y;
	}
};


int T, n, m, q;

int main(int argc, char *argv[]){
	ios::sync_with_stdio(false);
	scanf("%d%d%d", &n, &m, &q);
	vector<tuple<ll, int, int>> adds, querys;
	REP(i, m){
		int a, b;
		ll v;
		scanf("%d%d%lld", &a, &b, &v); a--;
		adds.eb(v, a, b);
	}
	REP(i, q){
		int a, b;
		ll v;
		scanf("%d%d%lld", &a, &b, &v); a--;
		querys.eb(v, a, b);
	}
	SegTreeDynamicLazy<handler> seg(n);
	vector<int> ptrs;
	ptrs.pb(seg.root);
	sort(ALL(adds));
	REP(i, m){
		int a, b, v;
		tie(v, a, b) = adds[i];
		ptrs.eb(seg.update(a, b, 1, ptrs.back(), 1));
	}
	REP(i, q){
		int x, y;
		ll j;
		tie(j, x, y) = querys[i];
		int l = 0, r = m;
		while(l+1 < r){
			int mid = (l+r)/2;
			if(seg.query(x, y, ptrs[mid]) < j) l = mid;
			else r = mid;
		}
		printf("%lld\n", get<0>(adds[l]));
	}
	return 0;
}