比太郎在打防御战。防御战的难度用一个 $\in [1,L]$ 的整数表示，这个值可以在任务开始时选择。在难度为 $\ell$（$1 \leq \ell \leq L$）的防御战中，怪物的生命值会是难度 $1$ 时的 $\ell$ 倍。

防御战持续 $ T $ 秒，期间会有 $ N $ 只怪物出现。每只怪物被分配一个从 $ 1 $ 到 $ N $ 的唯一编号。时间 $t$（$0 \leq t \leq T$）指战斗开始后 $t$ 秒的时刻。

怪物 $i$（$1 \leq i \leq N$）会在时间 $S_i$（$0 \leq S_i < T$）出现，强度为 $P_i$，且在难度 $\ell$ 下的生命值为 $\ell \times H_i$。

在防御战中，比太郎可以无限次执行以下动作：

• 选择当前在场的一只怪物并攻击它，这需要 $ 1 $ 秒的时间。怪物的生命值会减少 $ 1 $。一旦怪物的生命值降为 $ 0 $，它将被视为被击败并不再被攻击。

当时间到达 $ T $ 时，防御战结束，并按以下规则计算惩罚分：

• 设 $h_i$ 为时间 $ T $ 后怪物 $i$（$1 \leq i \leq N$）的剩余生命值。惩罚分为 $h_1 P_1 + h_2 P_2 + \cdots + h_N P_N$。

如果惩罚分小于等于任务指定的阈值 $ m $，则比太郎成功完成任务。由于更高难度会带来更好的奖励，比太郎希望确定他能完成任务的最髙难度等级。但阈值 $ m $ 是未知的，因此比太郎决定针对 $ Q $ 个候选阈值 $M_1, M_2, \ldots, M_Q$，分别找出能完成任务的最髙难度等级。

给定防御战的信息和候选阈值，请编写一个程序：对于每个阈值，判断任务是否可完成，并在可能的情况下找出可完成的最髙难度等级。

输入格式

• $N$ $L$ $T$
• $S_1$ $H_1$ $P_1$
• $S_2$ $H_2$ $P_2$
• $\vdots$
• $S_N$ $H_N$ $P_N$
• $Q$
• $M_1$
• $M_2$
• $\vdots$
• $M_Q$

输出格式

输出 $Q$ 行。在第 $j$ 行（$1 \leq j \leq Q$），输出当 $m = M_j$ 时能完成任务的最髙难度等级。如果在任何难度下都无法完成任务，则输出 $0$。

2 2 10
0 9 2
8 5 1
3
0
20
40

0
1
2

在难度为 $1$ 的防守战中，可以采取以下行动来达到 $4$ 的惩罚分。无法达到 $3$ 或更低的惩罚分。

此外，在难度为 $2$ 的防守战中，可以采取以下行动来达到 $26$ 的惩罚分。无法达到 $25$ 或更低的惩罚分。

此外，在此输入示例中，由于 $L = 2$，无法选择难度 $3$ 或更高的防御战。因此输出如下：

• 对于第一个阈值 $M_1 = 0$，无法在任何难度下完成任务，故第一行输出 $0$。
• 对于第二个阈值 $M_2 = 20$，最多能在难度 $1$ 下完成任务，故第二行输出 $1$。
• 对于第三个阈值 $M_3 = 40$，最多能在难度 $2$ 下完成任务，故第三行输出 $2$。

该样例满足子任务 $3\sim 8$ 的限制。

3 1 100000000000
60000000000 30000000000 1
30000000000 45000000000 1
10000000000 10000000000 1
1
0

0

该样例满足所有子任务的限制。

3 10000000 100000000
60000000 4 1
30000000 6 1
0 2 1
1
0

7000000

该样例满足子任务 $2\sim 8$ 的限制。

5 20 100
0 3 1
20 2 2
40 1 3
60 4 4
80 2 5
11
0
50
100
150
200
250
300
350
400
450
500

6
8
10
12
13
15
16
18
19
20
20

该样例满足子任务 $5\sim 8$ 的限制。

数据范围

• $1 \leq N \leq 6\,000$；
• $1 \leq L \leq 10\,000\,000$；
• $1 \leq T \leq 10^{18}$；
• $0 \leq S_i < T$（$1 \leq i \leq N$）；
• $1 \leq H_i$（$1 \leq i \leq N$）；
• $1 \leq P_i$（$1 \leq i \leq N$）；
• $H_1 P_1 + H_2 P_2 + \cdots + H_N P_N \leq 10^{11}$；
• $1 \leq Q \leq 1\,000\,000$；
• $0 \leq M_j \leq 10^{18}$（$1 \leq j \leq Q$）；
• $M_1 < M_2 < \cdots < M_Q$；
• 输入的所有值均为整数。

子任务

• $\text{Subtask 1 (1 pts)}$：$N \leq 30$，$Q = 1$，$M_1 = 0$，$L = 1$。
• $\text{Subtask 2 (3 pts)}$：$N \leq 30$，$Q = 1$，$M_1 = 0$。
• $\text{Subtask 3 (10 pts)}$：$N \leq 30$，$Q \leq 3$。
• $\text{Subtask 4 (10 pts)}$：$Q \leq 3$。
• $\text{Subtask 5 (35 pts)}$：$N \leq 30$。
• $\text{Subtask 6 (8 pts)}$：$N \leq 400$。
• $\text{Subtask 7 (20 pts)}$：$N \leq 1\,800$。
• $\text{Subtask 8 (13 pts)}$：无额外限制。