伟大的皇帝 Lord Pooty 决定退休，并想将王位传给他众多儿子中的一位。本着民主的精神，他决定通过投票来决定！他的王国由 $N$ 个城市组成，编号从 $0$ 到 $N - 1$。在这 $N$ 个城市中，有 $K$ 个是投票城市，可以在这些城市进行投票。第 $i$ 个投票城市为 $T_i$。

作为社会的一名负责任的成员，你认为履行公民义务是理所应当的。你必须前往其中一个指定的投票城市进行投票！共有 $E$ 条道路可以使用。第 $j$ 条道路单向连接城市 $U_j$ 到城市 $V_j$，通行费为 $C_j$。幸运的是，由于这次活动，当地城市开通了票务系统以降低旅行成本。

共有 5 种不同类型的票可供选择，编号从 1 型到 5 型。$x$ 型票可以将道路的通行费降低 $(10x)\%$。换句话说，如果使用了 $x$ 型票，道路的通行费将乘以 $1 - \frac{x}{10}$。

然而，关于票务有一些规则。你不能在同一条道路上使用多张票来叠加效果。你只允许在旅程开始时购买每种票最多一张。例如，你可以选择购买一张 1 型票和一张 2 型票，但不允许购买两张 2 型票。这是为了防止人们囤积票。你只允许在旅程开始时购买这些票。

你是一个大忙人，不幸的是，你不知道你可能从哪个城市开始旅程，也不知道票价。你列出了 $Q$ 种可能的情况，每种情况包含一个起始城市 $S$ 以及 5 种票的价格 $P_1, P_2, P_3, P_4$ 和 $P_5$。某些票可能根本无法获得，在这种情况下，票价将为 $-1$。

对于每种情况，如果可以通过道路到达某个投票城市，请找出前往其中一个投票城市的最低成本。请注意，并非每个城市都能从其他城市到达，你可能需要步行……

输入格式

程序必须从标准输入读取数据。

第一行包含 3 个整数 $N, E$ 和 $K$，分别代表城市数量、道路数量和投票城市数量。第二行包含 $K$ 个整数，第 $i$ 个整数代表第 $i$ 个投票城市 $T_i$。

接下来的 $E$ 行，每行包含 3 个整数。第 $j$ 行包含 $U_j, V_j$ 和 $C_j$，分别代表从 $U_j$ 到 $V_j$ 的单向道路及其通行费 $C_j$。保证 $C_j$ 是 10 的倍数。

下一行包含一个整数 $Q$，代表需要考虑的情况数量。

接下来的 $Q$ 行，每行包含 6 个整数 $S, P_1, P_2, P_3, P_4$ 和 $P_5$，分别代表起始城市以及 1 型到 5 型票的价格。注意，起始城市和票价在不同的情况下可能不同。

输出格式

程序必须打印到标准输出。

输出 $Q$ 行，每行一个整数，代表每种情况下前往投票城市的最低成本，顺序与输入一致。如果某种情况不存在路径，则输出 $-1$。

子任务

每个实例的最大执行时间为 1.0 秒。对于所有测试用例，输入满足以下范围：

• $1 \le N \le 5000$
• $0 \le E \le 10000$
• $1 \le Q \le 100$
• $0 \le K \le N$
• 对于所有 $1 \le i \le K$，$0 \le T_i < N$
• 对于所有 $1 \le i < j \le K$，$T_i \neq T_j$
• 对于所有 $1 \le i \le E$，$1 \le C_i \le 10^9$
• 对于所有 $1 \le i \le E$，$C_i$ 是 10 的倍数
• 对于所有 $1 \le i \le E$，$0 \le U_i, V_i < N$ 且 $U_i \neq V_i$
• 对于所有 $1 \le i \le 5$，$-1 \le P_i \le 10^9$

样例

样例输入 1

3 2 1
2
0 1 100
1 2 200
1
0 10 20 1000 2000 -1

样例输出 1

280

说明 1

在给出的唯一情况中，最优解是购买 2 型票并将其用于 $1 \to 2$ 的道路，购买 1 型票并将其用于 $0 \to 1$ 的道路。成本为 $200(1 - \frac{2}{10}) + 100(1 - \frac{1}{10}) + 10 + 20 = 160 + 90 + 10 + 20 = 280$。

样例输入 2

2 0 1
1
1
0 -1 -1 -1 -1 -1

样例输出 2

-1

说明 2

从你的起始点到唯一的投票城市没有道路。因此，输出 -1。

样例输入 3

6 3 2
4 5
0 4 100
1 4 200
2 5 300
4
0 -1 -1 -1 -1 -1
1 20 40 10 100 4
2 1 2 3 4 0
3 0 -1 0 0 0

样例输出 3

100
104
150
-1