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;

vector< int > nums;

template< typename T >
struct SegmentTree
{
  vector< T > seg, add;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, 0);
    add.assign(2 * sz - 1, 0);
  }

  T merge(T a, T b)
  {
    return (a + b);
  }

  void set(int k, int x)
  {
    seg[k + sz - 1] = x;
  }

  void build()
  {
    for(int k = sz - 2; k >= 0; k--) {
      seg[k] = merge(seg[2 * k + 1], seg[2 * k + 2]);
    }
  }

  T rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (0);
    if(a <= l && r <= b) return (seg[k] + add[k] * (nums[r] - nums[l]));
    return (merge(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),
                  rmq(a, b, 2 * k + 2, (l + r) >> 1, r)) +
            (add[k] * (min(nums[r], nums[b]) - max(nums[l], nums[a]))));
  }

  T rmq(int a, int b)
  {
    return (rmq(a, b, 0, 0, sz));
  }

  void rangeadd(int a, int b, T x, int k, int l, int r)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      add[k] += x;
      return;
    }
    rangeadd(a, b, x, 2 * k + 1, l, (l + r) >> 1);
    rangeadd(a, b, x, 2 * k + 2, (l + r) >> 1, r);
    seg[k] += x * (min(nums[r], nums[b]) - max(nums[a], nums[l]));
  }

  void rangeadd(int a, int b, T x)
  {
    rangeadd(a, b, x, 0, 0, sz);
  }
};

using int64 = long long;

int main()
{
  int N, M, Q;
  int A[100000], B[100000], C[100000];
  int X[100000], Y[100000];
  int64 Z[100000];
  int L[100000], R[100000];

  scanf("%d %d %d", &N, &M, &Q);

  for(int i = 0; i < M; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
    --A[i];
    nums.emplace_back(A[i]);
    nums.emplace_back(B[i]);
  }

  for(int i = 0; i < Q; i++) {
    scanf("%d %d %lld", &X[i], &Y[i], &Z[i]);
    --X[i];
    L[i] = 0, R[i] = M - 1;
    nums.emplace_back(X[i]);
    nums.emplace_back(Y[i]);
  }
  sort(begin(nums), end(nums));
  nums.erase(unique(begin(nums), end(nums)), end(nums));

  for(int i = 0; i < M; i++) {
    A[i] = lower_bound(begin(nums), end(nums), A[i]) - begin(nums);
    B[i] = lower_bound(begin(nums), end(nums), B[i]) - begin(nums);
  }
  for(int i = 0; i < Q; i++) {
    X[i] = lower_bound(begin(nums), end(nums), X[i]) - begin(nums);
    Y[i] = lower_bound(begin(nums), end(nums), Y[i]) - begin(nums);
  }

  vector< int > order(M);
  iota(begin(order), end(order), 0);
  sort(begin(order), end(order), [&](int a, int b)
  {
    return (C[a] < C[b]);
  });

  for(int i = 0; i < 19; i++) {
    vector< pair< int, int > > mid(Q);
    for(int j = 0; j < Q; j++) {
      mid[j] = {(L[j] + R[j]) / 2, j};
    }
    sort(begin(mid), end(mid));
    int tail = 0;
    SegmentTree< int64 > tree(nums.size());
    for(int j = 0; j < M; j++) {
      tree.rangeadd(A[order[j]], B[order[j]], 1);
      while(tail < Q && mid[tail].first == j) {
        const int idx = mid[tail].second;
        if(tree.rmq(X[idx], Y[idx]) >= Z[idx]) R[idx] = j;
        else L[idx] = j + 1;
        ++tail;
      }
    }
  }

  for(int i = 0; i < Q; i++) {
    printf("%d\n", C[order[L[i]]]);
  }
}