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>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename F,typename G,typename H>
vector<Int> parallelbinarysearch(Int n,Int q,
                                 F init,
                                 G apply,
                                 H check){
  vector<vector<Int> > C(q);
  vector<Int> L(n,-1),R(n,q);
  bool flg=1;
  while(flg){
    flg=0;
    init();
    for(Int i=0;i<n;i++)
      if(L[i]+1<R[i]) C[(L[i]+R[i])>>1].emplace_back(i);
    for(Int i=0;i<q;i++){
      flg|=!C[i].empty();
      apply(i);
      for(Int j:C[i]){
        if(check(j)) R[j]=i;
        else L[j]=i;
      }
      C[i].clear();
    }
  }
  return R;
}


template <typename T,typename E,typename F,typename G,typename H>
struct SegmentTree{
  Int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){}
  
  void init(Int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  inline T reflect(Int k){
    return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }
  inline void eval(Int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void thrust(Int k){
    for(Int i=height;i;i--) eval(k>>i);
  }
  inline void recalc(Int k){    
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }
  void update(Int a,Int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(Int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(Int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }
  T query(Int a,Int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(Int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }
};


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


template<typename T>
vector<T> compress(vector<T> v){
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  return v;
}

template<typename T>
map<T, Int> dict(const vector<T> &v){
  map<T, Int> res;
  for(Int i=0;i<(Int)v.size();i++)
    res[v[i]]=i;
  return res;
}

//INSERT ABOVE HERE
signed main(){
  using P = pair<Int, Int>;
  auto f=[&](P a,P b){return P(a.first+b.first,a.second+b.second);};
  auto g=[&](P a,Int b){return P(a.first+b*a.second,a.second);};
  auto h=[&](Int a,Int b){return a+b;};
  SegmentTree<P, Int, decltype(f), decltype(g), decltype(h)> seg(f,g,h,P(0,0),0);
  Int n,m,q;
  cin>>n>>m>>q;

  vector<Int> as(m),bs(m),vs(m);
  for(Int i=0;i<m;i++)
    cin>>as[i]>>bs[i]>>vs[i],as[i]--;

  {
    using T = tuple<Int, Int, Int>;
    vector<T> vt;
    for(Int i=0;i<m;i++) vt.emplace_back(vs[i],as[i],bs[i]);
    sort(vt.begin(),vt.end());
    for(Int i=0;i<m;i++) tie(vs[i],as[i],bs[i])=vt[i];
  }

  vector<Int> xs(q),ys(q),js(q);  
  for(Int i=0;i<q;i++)
    cin>>xs[i]>>ys[i]>>js[i],xs[i]--;

  vector<Int> ps;
  for(Int i=0;i<m;i++){
    ps.emplace_back(as[i]);
    ps.emplace_back(bs[i]);
  }  
  for(Int i=0;i<q;i++){
    ps.emplace_back(xs[i]);
    ps.emplace_back(ys[i]);
  }
  ps.emplace_back(0);
  ps.emplace_back(1000000007);
  ps=compress(ps);
  auto dc=dict(ps);
  
  vector<P> vp(ps.size()-1);
  for(Int i=0;i+1<(Int)ps.size();i++) vp[i]=P(0,ps[i+1]-ps[i]);
  
  auto init=
    [&](){
      seg.build(vp);
    };
  auto apply=
    [&](Int i){
      seg.update(dc[as[i]],dc[bs[i]],1);
    };
  auto check=
    [&](Int i){
      return seg.query(dc[xs[i]],dc[ys[i]]).first>=js[i];
    };

  auto ans=parallelbinarysearch(q,m,init,apply,check);
  for(Int i=0;i<q;i++) cout<<vs[ans[i]]<<"\n";
  cout<<flush;
  return 0;
}