King Gruff the Wolf rules over a happy, prosperous land inhabited by adorable Foxes. Unfortunately for them, he is not a nice king at all, and wants to make their lives miserable!</p>

His country has N (1 ≤ N ≤ 10⁵) cities, with M (0 ≤ M ≤ 10⁵) roads running amongst them. The ith road allows one to travel from city X_i to a different city Y_i (1 ≤ X_i, Y_i ≤ N), in that direction only, and has a length of L_i (1 ≤ L_i ≤ 10⁴) and a shutdown cost of C_i (1 ≤ C_i ≤ 10⁴). There may be multiple roads running between a pair of cities, even in the same direction.

King Gruff particularly dislikes the Foxes living in two different cities A and B (1 ≤ A, B ≤ N), and would like to make it more inconvenient (or even impossible) to travel from city A to city B. In particular, he’ll select a distance value D (1 ≤ D ≤ 10⁹), and then simultaneously shut down every single road in his kingdom which is part of at least one path from city A to city B with total length no more than D. For each such road, however, he’ll have to dig into his royal treasury and pay its shutdown cost. A path consists of a sequence of roads such that each road (except the first) starts at the city that the previous road ended at, and may visit a city or road multiple times.

Gruff is having trouble making up his mind about what value of D to choose, however - a larger value would make things more inconvenient for his Foxy subjects, but might cost him more money as well! As such, he’ll consider Q (1 ≤ Q ≤ 10⁵) different values, D₁, D₂, . . ., D_Q. For each one, he’d like to know how many tax dollars would need to be spent to shut down all roads which lie on at least one sufficiently short path from city A to city B. Since you don’t like Foxes either, you’ve agreed to help the Wolf write a program to calculate this!

입력 형식

The first line contains 4 integers, each separated by a space:</p>

• N (1 ≤ N ≤ 10⁵), the number of cities, followed by
• M (0 ≤ M ≤ 10⁵), the number of roads, followed by
• A (1 ≤ A ≤ N), the starting city, followed by
• B (1 ≤ B ≤ N), the ending city.

Each of the next M lines contain four space-separated integers X_i, Y_i, L_i, and C_i, describing the road from X_i to Y_i with length L_i and shutdown cost C_i (where 1 ≤ X_i, Y_i ≤ N, 1 ≤ L_i, C_i ≤ 10⁴). The next line contains Q (1 ≤ Q ≤ 10⁵), the number of different distance values to consider.

The next Q lines each contain one integer D_i (1 ≤ D_i ≤ 10⁹), which is the distance value to consider in shutting down roads.

출력 형식

The output consists of Q lines, each with one integer, representing the total cost required to shut down all necessary roads given a distance value of Di , for i = 1..Q

예제 입력 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

예제 입력 2

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

예제 출력 2

0