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 <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, long long> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define MAX_N (1<<19)
vector<int> seg[MAX_N*2-1];
vector<P> comp[MAX_N*2-1];

vector<int> xs;
long long query(int a, int b, int x, int k=0, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) {
    auto it = upper_bound(all(comp[k]), P(x, 1LL<<60));
    if (it == comp[k].begin()) return 0;
    return (--it)->_2;
  }
  long long s = 1LL*(xs[min(b, r)]-xs[max(a, l)])*(upper_bound(all(seg[k]), x) - seg[k].begin());
  s += query(a, b, x, k*2+1, l, (l+r)/2);
  s += query(a, b, x, k*2+2, (l+r)/2, r);
  return s;
}
void add(int a, int b, int x, int k=0, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return;
  comp[k].pb(P(x, xs[min(b, r)]-xs[max(a, l)]));
  if (a <= l && r <= b) {
    seg[k].pb(x);
    return;
  }
  add(a, b, x, k*2+1, l, (l+r)/2);
  add(a, b, x, k*2+2, (l+r)/2, r);
}

int N, M, Q;
int A[100000], B[100000], C[100000];
int X[100000], Y[100000];
long long J[100000];

signed main() {
  cin >> N >> M >> Q;
  rep(i, M) {
    cin >> A[i] >> B[i] >> C[i];
    A[i]--;
    xs.pb(A[i]), xs.pb(B[i]);
  }
  rep(i, Q) {
    cin >> X[i] >> Y[i] >> J[i];
    X[i]--;
    xs.pb(X[i]), xs.pb(Y[i]);
  }
  sort(all(xs)); uniq(xs);
  rep(i, M) A[i] = index(xs, A[i]), B[i] = index(xs, B[i]);
  rep(i, Q) X[i] = index(xs, X[i]), Y[i] = index(xs, Y[i]);

  rep(i, M) add(A[i], B[i], C[i]);
  rep(i, MAX_N*2-1) {
    sort(all(seg[i]));
    sort(all(comp[i]));
    if (!comp[i].empty()) rep(j, comp[i].size()-1) comp[i][j+1]._2 += comp[i][j]._2;
  }

  rep(i, Q) {
    int l = X[i], r = Y[i];
    long long k = J[i];
    long long lo = 0, hi = INF;
    while (hi - lo > 1) {
      int mid = (lo + hi) / 2;
      if (query(l, r, mid) >= k) hi = mid;
      else lo = mid;
    }
    cout << hi << "\n";
  }
  return 0;
}