勇敢的英雄 Bitaro 即将参加“防御战”任务，以保护村庄免受怪物的侵害。防御战的难度由一个 $1$ 到 $L$ 之间的整数（包含 $1$ 和 $L$）表示，该值可以在挑战开始时选择。在难度为 $\ell$ ($1 \le \ell \le L$) 的防御战中，怪物的生命值（HP）是难度为 $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$。

在防御战期间，Bitaro 可以执行任意次数的以下操作： * 选择当前存在的一只怪物并对其进行攻击，这需要 $1$ 秒。怪物的生命值减少 $1$。一旦怪物的生命值达到 $0$，它就被视为被击败，且不再会被攻击。

当时间达到 $T$ 时，防御战结束，惩罚分数计算如下： * 令 $h_i$ 为怪物 $i$ ($1 \le i \le N$) 在时间 $T$ 之后立即的生命值。惩罚分数计算为 $h_1P_1 + h_2P_2 + \dots + h_N P_N$。

如果惩罚分数小于或等于任务指定的阈值 $m$，则 Bitaro 成功完成任务。

由于更高的难度会带来更好的奖励，Bitaro 想要确定他能完成任务的最高难度等级。然而，阈值是预先未知的。因此，Bitaro 决定针对 $Q$ 个候选阈值 $M_1, M_2, \dots, 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 \le j \le Q$)，输出当 $m = M_j$ 时能完成任务的最高难度等级。如果无法在任何难度等级下完成任务，则输出 $0$。

数据范围

• $1 \le N \le 6\,000$
• $1 \le L \le 10\,000\,000$
• $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_1P_1 + H_2P_2 + \dots + H_N P_N \le 10^{11}$
• $1 \le Q \le 1\,000\,000$
• $0 \le M_j \le 10^{18}$ ($1 \le j \le Q$)
• $M_1 < M_2 < \dots < M_Q$
• 给定值均为整数。

子任务

1. (1 分) $N \le 30, Q = 1, M_1 = 0, L = 1$
2. (3 分) $N \le 30, Q = 1, M_1 = 0$
3. (10 分) $N \le 30, Q \le 3$
4. (10 分) $Q \le 3$
5. (35 分) $N \le 30$
6. (8 分) $N \le 400$
7. (20 分) $N \le 1\,800$
8. (13 分) 无附加限制

样例

样例输入 1

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

样例输出 1

0
1
2

样例输入 2

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

样例输出 2

0

样例输入 3

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

样例输出 3

7000000

样例输入 4

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

样例输出 4

6
8
10
12
13
15
16
18
19
20
20

样例输入 5

15 10000000 1000000000000
160278118759 43084 33592
442653603914 19490 23090
824219815410 50858 89563
502303340628 56629 45080
495062829942 87342 28821
234536700105 45384 34328
396080693809 78081 50812
734374391045 40873 92012
122606844331 25451 30426
204076581972 58431 13989
495156368673 54276 41670
812963939390 27614 50228
405067019838 96324 18477
464546304875 67562 45956
528559327980 41759 15546
10
216000000000000
1728000000000000
5832000000000000
13824000000000000
27000000000000000
46656000000000000
74088000000000000
110592000000000000
157464000000000000
216000000000000000

样例输出 5

995176
1135557
1431775
1824183
2359362
3059523
3942014
5106209
6594716
8448125