狼王格鲁夫（King Gruff）统治着一片快乐繁荣的土地，这里居住着可爱的狐狸。不幸的是，他一点也不友好，并且想让狐狸们的生活变得痛苦不堪！

他的国家有 $N$（$1 \le N \le 10^5$）座城市，城市之间有 $M$（$0 \le M \le 10^5$）条道路。第 $i$ 条道路允许人们从城市 $X_i$ 单向通行到另一个城市 $Y_i$（$1 \le X_i, Y_i \le N$），其长度为 $L_i$（$1 \le L_i \le 10^4$），关闭成本为 $C_i$（$1 \le C_i \le 10^4$）。在一对城市之间可能存在多条道路，甚至方向也相同。

格鲁夫特别讨厌居住在两个不同城市 $A$ 和 $B$（$1 \le A, B \le N$）的狐狸，并希望让从城市 $A$ 到城市 $B$ 的出行变得更加不便（甚至不可能）。具体来说，他会选择一个距离值 $D$（$1 \le D \le 10^9$），然后同时关闭王国中所有满足以下条件的道路：该道路是至少一条从城市 $A$ 到城市 $B$ 且总长度不超过 $D$ 的路径的一部分。然而，对于每一条这样的道路，他都必须从皇家国库中拨款并支付其关闭成本。一条路径由一系列道路组成，使得每条道路（第一条除外）都始于前一条道路结束的城市，并且可以多次访问同一个城市或同一条道路。

然而，格鲁夫在决定选择哪个 $D$ 值时遇到了困难——较大的值会让他的狐狸子民更加不便，但同时也可能让他花费更多的资金！因此，他将考虑 $Q$（$1 \le Q \le 10^5$）个不同的值 $D_1, D_2, \dots, D_Q$。对于每一个值，他都想知道需要花费多少税款来关闭所有位于至少一条足够短的从城市 $A$ 到城市 $B$ 的路径上的道路。既然你也不喜欢狐狸，你同意帮助狼王编写一个程序来计算这个费用！

输入格式

第一行包含 $4$ 个整数，每个整数之间用空格分隔：

• $N$（$1 \le N \le 10^5$），城市的数量，后跟
• $M$（$0 \le M \le 10^5$），道路的数量，后跟
• $A$（$1 \le A \le N$），起点城市，后跟
• $B$（$1 \le B \le N$），终点城市。

接下来的 $M$ 行，每行包含四个空格分隔的整数 $X_i, Y_i, L_i$ 和 $C_i$，描述从 $X_i$ 到 $Y_i$ 的道路，其长度为 $L_i$，关闭成本为 $C_i$（其中 $1 \le X_i, Y_i \le N$，$1 \le L_i, C_i \le 10^4$）。

下一行包含 $Q$（$1 \le Q \le 10^5$），表示需要考虑的不同距离值的数量。

接下来的 $Q$ 行，每行包含一个整数 $D_i$（$1 \le D_i \le 10^9$），表示关闭道路时需要考虑的距离值。

输出格式

输出包含 $Q$ 行，每行一个整数，表示在给定距离值 $D_i$（对于 $i = 1 \dots Q$）时，关闭所有必要道路所需的总成本。

数据范围

对于输入数据，满足以下条件：

• 对于占总分最多 20% 的测试用例，$N \le 500$；
• 对于占总分最多 20% 的测试用例，$Q = 1$；
• 对于占总分最多 80% 的测试用例，$Q \le 20$。

样例

输入样例 1

4 5 1 3
1 2 5 1
1 2 8 50
2 3 2 15
3 1 80 1000
3 4 1 1
4
8
6
90
94

输出样例 1

16
0
66
1066

说明 1

该国的地图如下图所示，每条道路上仅标有其长度：

如果 $D = 8$，则需要关闭第一条和第三条道路，因为它们都是从城市 1 到城市 3 长度为 7 的路径的一部分。这导致总成本为 $1 + 15 = 16$。

如果 $D = 6$，则不需要关闭任何道路，因为不存在从城市 1 到城市 3 且总长度小于或等于 6 的路径。

如果 $D = 90$，则前三条道路都需要关闭。

如果 $D = 94$，则第四条道路也必须关闭，因为它位于一条从城市 1 到城市 3 长度恰好为 94 的路径上，该路径由第一条、第三条、第四条、第一条，然后是第三条道路组成。

输入样例 2

4 3 1 2
2 1 1 1
3 4 10000 10000
4 3 10000 10000
1
1000000000

输出样例 2

0

说明 2

该国的地图如下图所示：

显而易见，狐狸们已经遇到了麻烦，因为根本不存在从城市 1 到城市 2 的路径！因此，对于任何 $D$ 值，格鲁夫都不需要关闭任何道路。