问题陈述
你被给予 N 空数组, t_1, ..., t_n。首先,你执行 M 查询如下。
- 添加一个值 v 到数组 t_i (a \leq i \leq b)
- 输出 j- 对所有值进行排序的序列号 t_i (x \leq i \leq y)
输入
数据集的格式如下。
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
第一行包含三个整数 N (1 \leq N \leq 10^9), M (1 \leq M \leq 10^5)和 Q (1 \leq Q \leq 10^5)。以下每一项 M 行由三个整数组成 a_i, b_i 和 v_i (1 \leq a_i \leq b_i \leq N, 1 \leq v_i \leq 10^9)。最后是以下内容 Q 行给出输出查询列表,每行由三个整数组成 x_i, y_i 和 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|).
输出
对于每个输出查询,在一行中打印 j- 第一个数字。
示例输入 1
5 4 1 1 5 1 1 1 3 4 5 1 3 4 2 1 3 4
样本输入 1 的输出
2
之后 M执行第一个查询,每个 t_i 如下:
[1,3], [1], [1,2], [1,1,2], [1,1]序列排序值 t_1, t_2 和 t_3 是 [1,1,1,2,3]。在数列中,第 4 个数字是 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