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

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

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

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

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

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

• 设 $h_i$ 为时间 $T$ 后怪物 $i$（$1\le i\le N$）的剩余生命值。惩罚分为 $h_1{P}_1+h_2{P}_2+\cdots +h_N{P}_N$。

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

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

输入格式

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

输出格式

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

样例一

input

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

output

0
1
2

explanation

在难度为 $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$ 的限制。

样例二

input

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

output

0

explanation

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

样例三

input

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

output

7000000

explanation

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

样例四

input

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

output

6
8
10
12
13
15
16
18
19
20
20

explanation

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

数据范围

• $1\le N\le 6000$；
• $1\le L\le 10000000$；
• $1\le T\le {10}^{18}$；
• $0\le S_i<T$（$1\le i\le N$）；
• $1\le H_i$（$1\le i\le N$）；
• $1\le P_i$（$1\le i\le N$）；
• $H_1{P}_1+H_2{P}_2+\cdots +H_N{P}_N\le {10}^{11}$；
• $1\le Q\le 1000000$；
• $0\le M_j\le {10}^{18}$（$1\le j\le Q$）；
• $M_1<M_2<\cdots <M_Q$；
• 输入的所有值均为整数。

子任务

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