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>
#define int long long
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

typedef long long ll;

template<class Handler>
struct segtree_lazy{
	using val_t = typename Handler::val_t;
	using opr_t = typename Handler::opr_t;
	int N;
	vector<val_t> val;
	vector<opr_t> lazy;
	segtree_lazy(){}
	segtree_lazy(int n){init(n);}
	segtree_lazy(const vector<val_t>& vc){init(vc);}
	void init(int n){
		N=1;
		while(N<n) N*=2;
		val .assign(N*2,val_t::e());
		lazy.assign(N*2,opr_t::e());
	}
	void init(const vector<val_t>& vc){
		int n = vc.size();
		N=1;
		while(N<n) N*=2;
		val .assign(N*2,val_t::e());
		rep(i,n) val[i+N] = vc[i];
		for(int i=N-1;i>0;i--) val[i] = val[i*2] + val[i*2+1];
		lazy.assign(N*2,opr_t::e());
	}
	val_t realvalue(int k,int l,int r){
//		return Handler::act(lazy[k],val[k]);
		return Handler::act(lazy[k],val[k],k,l,r);
	}

	val_t query(int a,int b,int l=0,int r=-1,int k=1){	//query_calc
		if(r==-1) r=N;
		if(b<=l||r<=a) return val_t::e();
		if(a<=l&&r<=b) return realvalue(k,l,r);
		propagate(l,r,k);
		val_t ret = query(a,b,l,(l+r)/2,k*2) + query(a,b,(l+r)/2,r,k*2+1);
		val[k] = realvalue(k*2,l,(l+r)/2) + realvalue(k*2+1,(l+r)/2,r);
		return ret;

	}
//	val_t query_leftassoc(){}
	void update(int a,int b,const opr_t &x,int l=0,int r=-1,int k=1){	//query_update
		if(r==-1) r=N;
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			Handler::setg2fg(x,lazy[k]);
			return;
		}
		propagate(l,r,k);
		update(a,b,x,l,(l+r)/2,k*2);
		update(a,b,x,(l+r)/2,r,k*2+1);
		val[k] = realvalue(k*2,l,(l+r)/2) + realvalue(k*2+1,(l+r)/2,r);
	}
	void propagate(int l,int r,int k){	//opr_child -> opr_parent * opr_child		parent after child
		Handler::setg2fg(lazy[k],lazy[k*2  ]);
		Handler::setg2fg(lazy[k],lazy[k*2+1]);
		lazy[k] = opr_t::e();
	}
};

struct handler{
	/*
		range add
		range sum
		??????????????????????????°??????????????????????????????sum?????¨???
	*/
	struct val_t{
		ll x;
		ll w;
		val_t(){*this = e();}
		val_t(ll x,ll w):x(x),w(w){}

		const static val_t e(){
			return val_t(0,0);
		}
		val_t operator+(const val_t &r) const {
			return val_t(x+r.x,w+r.w);
		}
		friend ostream& operator<<(ostream& o,const val_t& d){return o<<d.x;}
	};

	struct opr_t{
		ll x;
		opr_t(){*this = e();}
		opr_t(ll x):x(x){}

		const static opr_t e(){
			return opr_t(0);
		}
		friend ostream& operator<<(ostream& o,const opr_t& d){return o<<d.x;}
	};

	static void getfg(const opr_t &f, const opr_t &g){

	}
	/*
		??????????????????????????¨???????°?????????£???,??????????\???????????????????setg2fg?????´??\??????
		???????????????????????? g = getfg(f,g)
	*/
	static void setg2fg(const opr_t &f, opr_t &g){	//g -> fg		f after g
		if(f.x != -1) g.x += f.x;
	}
	static val_t act(const opr_t &f, const val_t &v,int k,int l,int r){
		return val_t(v.x + f.x*v.w,v.w);
	}
	// static void act(opr_t &f, val_t &v){
	// 	if(f.x == -1) return;
	// 	v.x = f.x;
	// 	f.x = -1;
	// }
};

using val_t = handler::val_t;
using opr_t = handler::opr_t;


int N,M,Q;
const int MX = 400010;
int l[MX],r[MX],v[MX];
int x[MX],y[MX],k[MX];
vector<int> v2is[MX];
vector<int> xs;
vector<int> vs;

int getxid(int x){
	return lower_bound(all(xs),x) - xs.begin();
}
int getvid(int v){
	return lower_bound(all(vs),v) - vs.begin();
}

signed main(){
	cin>>N>>M>>Q;
	rep(i,M){
		cin>>l[i]>>r[i]>>v[i];
		l[i]--;
		xs.pb(l[i]);
		xs.pb(r[i]);
		vs.pb(v[i]);
	}
	sort(all(vs));vs.erase(unique(vs.begin(),vs.end()),vs.end());

	rep(i,Q){
		cin>>x[i]>>y[i]>>k[i];
		x[i]--;
		xs.pb(x[i]);
		xs.pb(y[i]);
	}

	xs.pb(0);
	xs.pb(N);
	sort(all(xs));xs.erase(unique(xs.begin(),xs.end()),xs.end());

	int V = vs.size();
	int X = xs.size();

	rep(i,M){
		l[i] = getxid(l[i]);
		r[i] = getxid(r[i]);
		v[i] = getvid(v[i]);
	}
	rep(i,Q){
		x[i] = getxid(x[i]);
		y[i] = getxid(y[i]);
	}

	rep(i,M){
		v2is[v[i]].pb(i);
	}

	vector<val_t> be;
	rep(i,X-1){
		ll w = xs[i+1] - xs[i];
		be.pb(val_t(0,w));
	}

	vector<int> lbs(Q,-1),ubs(Q,V);
	while(true){
		vector<int> mids;
		vector<vector<int>> m2qs(V);
		bool done = 1;
		rep(i,Q){
			if(lbs[i]+1 == ubs[i]) continue;
			done = 0;
			int m = (lbs[i]+ubs[i])/2;
			m2qs[m].pb(i);
		}
		if(done) break;

		segtree_lazy<handler> seg(be);

		rep(v,V){
			//add v
			for(int i:v2is[v]){
				seg.update(l[i],r[i],opr_t(1));
			}

			for(int q:m2qs[v]){
				if(seg.query(x[q],y[q]).x >= k[q]) ubs[q] = v;
				else lbs[q] = v;
			}
		}
	}

	rep(i,Q) cout<<vs[ubs[i]]<<endl;
}