题目背景

Alek 岁在操场上跑圈。他看到有人超过他，很不爽。于是他采取了以下策略：

题目描述

在长度为 $m$ 的环形操场上有 $n$ 个人，第 $i$ 个人在 $t_i$ 时刻从位置 $p_i$ 出发以 $v_i$ 单位长度每秒的速度移动。现在 $0$ 时刻 Alek 岁在位置 $0$ 处，速度为 $0$，会跟着经过他的速度最快的人移动。$q$ 次询问 $T_i$ 时刻 Alek 岁的移动距离。可以证明这是一个整数。

注：从位置 $0$ 出发逆时针方向 $x$（$0\leq x < m$）单位长度的位置称为位置 $x$。所有人的运动方向都是逆时针。

多组数据。

输入格式

第一行一个整数 $T$ 表示数据组数。对于每组数据：

• 第一行三个整数 $n, m, q$，分别表示人数，操场长度和询问个数。
• 接下来 $n$ 行，每行三个整数 $p_i, v_i, t_i$，分别表示第 $i$ 个人出发时的位置，移动速度（单位长度每秒）和出发时间。
• 接下来 $q$ 行，每行一个整数 $T_i$ 表示一次询问。

输出格式

对于每个询问，输出一行一个整数表示答案。

1
3 30 8
0 2 1
6 5 2
25 4 4
1
5
9
10
11
12
13
14

0
8
16
19
23
27
31
36

提示

对于所有数据，$1\leq T\leq 10 ^ 3$，$1\leq n, \sum n\leq 5\times 10 ^ 5$，$1\leq m, q, \sum q \leq 10 ^ 6$，$1\leq v_i, t_i, T_i\leq 10 ^ 9$，$0\leq p_i < m$。保证 $t_i$ 单调不降，$T_i$ 单调递增。

• 子任务 1（$10$ 分）：$n\leq 5$。
• 子任务 2（$10$ 分）：$n\leq 50$。
• 子任务 3（$20$ 分）：$n\leq 500$。
• 子任务 4（$20$ 分）：$n\leq 5\times 10 ^ 3$。
• 子任务 5（$20$ 分）：$n\leq 5\times 10 ^ 4$。
• 子任务 6（$20$ 分）：无特殊限制。

请注意，子任务并没有保证 $\sum q$ 的数量级。

本题 IO 量较大，建议使用 scanf/printf 或关闭流同步的 cin/cout 或快速读入和快速输出。

Source：NFLSPC #6 I by Alex_Wei