题目描述

你所在的国家的国家主席 $\bf{Lord\ Pooty}$ 将要退休了！他希望选择他的一个儿子作为他的继承人，出于各方面因素的考虑，他决定进行一次投票！他所在的国家中共有 $N$ 个国家，编号从 $0$ 到 $N-1$，其中 $K$ 个城市是可以投票的，第 $i$ 个可以投票的城市编号为 $T_i$。

你认为，投票是你作为公民应该做的义务。于是你决定去某一个能投票的城市参与投票！所有城市之间有 $E$ 条公路，第 $j$ 条公路单向从城市 $U_j$ 通往城市 $V_j$，通过这条公路需要交过路税 $C_j$。幸运的是，为了更好的完成投票，国家颁布了一系列过路税优惠政策。

具体的来说，你有 $5$ 种优惠券可以购买，使用第 $x$ 种优惠券通过一条过路税为 $y$ 的公路时，只需要付 $y \times (10x)\%$。但是，由于很多人都想投票，需要使用优惠券，所以每一种优惠券你最多只能买 $1$ 张。

你是个大忙人，你既不知道从哪个城市出发，也不知道每种优惠券的价格。你现在设想了 $Q$ 种情况，包括出发城市 $S$ 和优惠券价格 $P_1,P_2,P_3,P_4$ 和 $P_5$。在有些情况下某些优惠券甚至已经被抢光了，你不能购买它们，此时这些无法购买的优惠券的价格将被表示为 $-1$。

现在你需要分别对这 $Q$ 种情况，输出到达某一个投票城市的最小花费。请注意，你不一定总是能通过公路到达某一个投票城市，如果不能到达，你应该输出 $-1$。

输入格式

第一行，三个整数 $N,E,K$。

第二行，$K$ 个整数，表示 $T_i$。

接下来 $E$ 行，每行三个整数 $U_j,V_j,C_j$。保证 $C_j$ 是 $10$ 的倍数。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行 $6$ 个整数 $S,P_1,P_2,P_3,P_4,P_5$。

输出格式

共 $Q$ 行，每行一个整数表示答案。

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

280

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

-1

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

100
104
150
-1

提示

【样例 #1 解释】

该样例满足 $\tt{Subtask\ 4,5,7,8}$ 的限制。

对于这种情况，最佳方案是在 $1 \to 2$ 的道路上使用一张 $2$ 类优惠券，在 $0 \to 1$ 的道路上使用一张 $1$ 类优惠券，花费为 $200 \times (1 - \frac{2}{10})+100 \times (1 - \frac{1}{10})\%+10+20=160+90+10+20=280$。

【样例 #2 解释】

该样例满足所有 $\tt{Subtask}$ 的限制。

没有道路可以从出发城市到达一个投票城市，所以输出 $-1$。

【样例 #3 解释】

该样例满足 $\tt{Subtask\ 7,8}$ 的限制。

【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 5000,0 \le E \le 10000,1 \le Q \le 100,0 \le K \le N,0 \le T_i < N,1 \le C_i \le 10^9,-1 \le P_i \le 10^9$，且对于所有 $1 \le i < j \le K$，有 $T_i \not = T_j$；对于所有 $1 \le i \le E$，保证 $C_i$ 是 $10$ 的倍数，$0 \le U_i,V_i < N,U_i\not=V_i$。