题目背景

本题测试点极大，评测时可能需要等待较长时间加载测试点。

题目描述

比太郎在打防御战。防御战的难度用一个 $\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

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

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

提示

子任务

样例解释 $1$

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

时间	事件
$0$	怪物 $1$（生命值 $9$）出现。
$0 \sim 8$	攻击怪物 $1$ 共 $8$ 次。怪物 $1$ 的生命值从 $9$ 降至 $1$。
$8$	怪物 $2$（生命值 $5$）出现。
$8 \sim 9$	攻击怪物 $2$ $1$ 次。怪物 $2$ 的生命值从 $5$ 降至 $4$。
$9 \sim 10$	攻击怪物 $1$ $1$ 次。怪物 $1$ 的生命值从 $1$ 降至 $0$。
$10$	怪物 $1$ 被击败。
	防守战结束。惩罚分为 $0 \times P_1 + 4 \times P_2 = 4$。

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

时间	事件
$0$	怪物 $1$（生命值 $18$）出现。
$0 \sim 8$	攻击怪物 $1$ 共 $8$ 次。怪物 $1$ 的生命值从 $18$ 降至 $10$。
$8$	怪物 $2$（生命值 $10$）出现。
$8 \sim 10$	攻击怪物 $1$ 共 $2$ 次。怪物 $1$ 的生命值从 $10$ 降至 $8$。
$10$	防守战结束。惩罚分为 $8 \times P_1 + 10 \times P_2 = 26$。

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

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

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

样例解释 $2$

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

样例解释 $3$

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

样例解释 $4$

该样例满足子任务 $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)}$：无额外限制。