题目描述

给出 $N$ 个空的可重集，记为 $t_1,\dots,t_N$。

一开始，执行 $M$ 次如下述的操作：

• 向所有满足 $a\le i\le b$ 的可重集 $t_i$ 中放入一个数 $v$。

接下来，处理 $Q$ 次如下述的查询：

• 求出所有满足 $x\le i\le y$ 的可重集 $t_i$ 中第 $j$ 小的数。

输入格式

数据集的格式如下：

$N$ $M$ $Q$

$a_1$ $b_1$ $v_1$

$\dots$

$a_M$ $b_M$ $v_M$

$x_1$ $y_1$ $j_1$

$\dots$

$x_Q$ $y_Q$ $j_Q$

第一行包括三个整数 $N,M,Q$。接下来的 $M$ 行，每行包括三个整数 $a_i,b_i,v_i$。最后 $Q$ 行，每行包括三个整数 $x_i,y_i,j_i$。

输出格式

对于每一个询问，输出第 $j$ 小的数。

输入输出样例

输入 #1

5 4 1
1 5 1
1 1 3
4 5 1
3 4 2
1 3 4

输出 #1

2

输入 #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

输出 #2

11
11
33
44

说明/提示

样例说明

对于样例 1，$M$ 次查询之后，$N$ 个可重集是这样的：

{1,3}, {1}, {1,2}, {1,1,2}, {1,1}

$t_1,t_2,t_3$ 的并集是 $\{1,1,1,2,3\}$，所以第 $4$ 小的数是 $2$。

数据范围

对于 $100\%$ 的数据，$1\le N\le 10^9$，$1\le M,Q\le 10^5$，$1\le a_i\le b_i\le N$，$1\le v\le 10^9$，$1\le x_i\le y_i\le N$，$1\le j_i\le \sum\limits_{x_i\le k\le y_i}|t_k|$。