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;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 1<<29;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef long long ll;
typedef pair<int,int> pii;
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<int N,class Tuple> void out(ostream&,const Tuple&) {}
template<int N,class Tuple,class,class ...Ts> void out(ostream &os,const Tuple &t) {
	if(N)os<<","; os<<get<N>(t); out<N+1,Tuple,Ts...>(os,t);
}
template<class ...Ts> ostream& operator<<(ostream &os, const tuple<Ts...> &t) {
  os<<"("; out<0,tuple<Ts...>,Ts...>(os,t); os<<")"; return os;
}
template<class T>void output(T *a, int n) {REP(i,n){if(i)cout<<",";cout<<a[i];}cout<<endl;}
template<class T>void output(T *a, int n,int m) { REP(i,n) output(a[i],m);}

struct AddQuery {
  int a,b,v;
  int a_id, b_id;
  void in() {
    scanf("%d%d%d",&a,&b,&v);
  }
  bool operator<(const AddQuery &rhs) const {
    return v < rhs.v;
  }
} addQuery[100000];

struct OutputQuery {
  int x,y;
  int x_id, y_id;
  ll j;
  int ans;
  void in() {
    scanf("%d%d%lld",&x,&y,&j);
  }
} outputQuery[100000];

int id[100000];
ll imos[500001];
int diff[500001];
struct P {
  int val;
  int type;
  int id;
  bool operator<(const P &rhs) const {
    return val < rhs.val;
  }
} p[500001], tmp1[500001], tmp2[500001];
ll sum[500001];
bool flag[100000];

void solve(int l, int r, int ql, int qr, int pl, int pr) {
  if (l+1 == r) {
    for (int i=ql; i<qr; ++i) {
      outputQuery[id[i]].ans = addQuery[l].v;
    }
    return;
  }
  
  int pre = -1;
  int cnt = -1;
  for (int i=pl; i<pr; ++i) {
    if (i!=pl) assert(p[i-1].val<=p[i].val);
    const P &q = p[i];
    if (pre != q.val) {
      cnt++;
      if (cnt) diff[cnt-1] = q.val - pre;
      pre = q.val;
    }
    if (p[i].type == 0) addQuery[q.id].a_id = cnt;
    else if (p[i].type == 1) addQuery[q.id].b_id = cnt;
    else if (p[i].type == 2) outputQuery[q.id].x_id = cnt;
    else outputQuery[q.id].y_id = cnt;
    // cout << tpl(i,p[i].type,p[i].id,p[i].val,cnt) << endl;
  }
  cnt++;
  int mid = (l+r)>>1;
  for (int i=l; i<mid; ++i) {
    imos[addQuery[i].a_id]++;
    imos[addQuery[i].b_id]--;
  }
  REP(i,cnt) {
    imos[i+1] += imos[i];
    sum[i+1] = sum[i] + imos[i];
    if (i) sum[i+1] += imos[i-1] * (diff[i-1]-1);
  }

  // cout << tpl(l,r,ql,qr,pl,pr) << endl;
  // output(sum,cnt+1);
  //   assert(2*(r-l+qr-ql) == pr-pl);
  REP(i,cnt+1) imos[i] = 0;
  int bound = partition(id+ql, id+qr,
                        [](int i) {
                          int x = outputQuery[i].x_id + 1;
                          int y = outputQuery[i].y_id + 1;
                          ll sm = sum[y]-sum[x];
                          // cout << i << " " << sm << endl;
                          flag[i] = 1;
                          if (sm >= outputQuery[i].j) return 1;
                          outputQuery[i].j = outputQuery[i].j - sm;
                          flag[i] = 0;
                          return 0;
                        }) - id;
  static int static_mid;
  static_mid = mid;
  int pbound = stable_partition(p+pl, p+pr,
                         [](const P &q) {
                           if (q.type <= 1) {
                             return q.id < static_mid;
                           } else {
                             return flag[q.id];
                           }
                         }) - p;
  solve(l,mid,ql,bound,pl,pbound);
  solve(mid,r,bound,qr,pbound,pr);
}

int main() {
  int n,m,q;
  while(cin >> n >> m >> q) {
    REP(i,m)addQuery[i].in();
    REP(i,q)outputQuery[i].in();
    sort(addQuery, addQuery+m);
    int cnt = 0;
    REP(i,m) {
      p[cnt++] = P({addQuery[i].a, 0, i});
      p[cnt++] = P({addQuery[i].b+1, 1, i});
    }
    REP(i,q) {
      p[cnt++] = P({outputQuery[i].x-1, 2, i});
      p[cnt++] = P({outputQuery[i].y, 3, i});
    }
    sort(p,p+cnt);
    iota(id,id+q,0);
    solve(0,m,0,q,0,cnt);
    REP(i,q) printf("%d\n",outputQuery[i].ans);
  }
}