Problem Description

This problem is a translation of CCO 2014 Day1 T2 "King Gruff"

King Gruff rules over a prosperous and happy territory inhabited by adorable foxes. Unfortunately for the foxes, he is not a good king and wants to make their lives miserable.

His kingdom has $N$ cities connected by $M$ roads. The $i$-th road allows travel from city $X_i$ to another city $Y_i$ in one direction only, with a length of $L_i$ and a closing fee of $C_i$. There may be multiple roads connecting the same pair of cities in the same direction.

King Gruff particularly dislikes the foxes living in two different cities $A$ and $B$ and wants to make it difficult, if not impossible, for them to travel from city $A$ to city $B$. Specifically, he will choose a distance $D$ and close certain roads in his kingdom. A road will be closed if it is part of a path from city $A$ to city $B$ with a total length not exceeding $D$. For each such road, he will use the royal treasury to pay its closing fee. A path consists of a sequence of roads, where each road's start is the previous road's end, and may visit the same city or use the same road multiple times.

Gruff is undecided on which $D$ to choose. Larger values of $D$ can make his fox subjects more inconvenienced, but may cost him more money! Therefore, he has thought of $Q$ different values $D_1, D_2, ..., D_Q$, and for each value, he wants to know the minimum cost required to meet his requirements. Since you also dislike foxes, you agree to help him write a program to calculate the minimum cost.

Input Format

The first line contains four space-separated integers $N, M, A, B$, representing the number of cities, the number of roads, the starting city, and the ending city, respectively.

The next $M$ lines contain four space-separated integers $X_i, Y_i, L_i, C_i$, representing a road from $X_i$ to $Y_i$ with length $L_i$ and closing fee $C_i$.

The next line contains an integer $Q$, representing the number of queries.

The next $Q$ lines contain an integer $D_i$ representing the distance parameter as described in the problem.

Output Format

The output should consist of $Q$ lines, each representing the total cost of closing all necessary roads for the distance parameter $D_i$ (1 ≤ i ≤ Q).

Sample Input and Output

Input Sample #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

Output Sample #1

16
0
66
1066

Input Sample #2

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

Output Sample #2

0

Notes/Hints

The kingdom is illustrated below, with each road labeled by its length.

If $D = 8$, the first and third roads need to be closed, as they are part of a path from city 1 to city 3 with a length of 7, with a total cost of $1 + 15 = 16$.

If $D = 6$, no roads need to be closed, as there is no path from city 1 to city 3 with a length less than or equal to 6.

If $D = 90$, the first three roads need to be closed.

If $D = 94$, the fourth road also needs to be closed, as it is part of a path from city 1 to city 3 with a length of exactly 94, consisting of the first, third, fourth, first, and third roads.

The kingdom is illustrated below:

As you can see, the foxes are already in trouble, as there is no path from city 1 to city 2, so for any $D$, King Gruff does not need to close any roads.

For at most $20\%$ of the data, $1 ≤ N ≤ 500$;

For at most $20\%$ of the data, $Q = 1$;

For at most $80\%$ of the data, $1 ≤ Q ≤ 20$;

For $100\%$ of the data, $1 ≤ X_i, Y_i, A, B ≤ N ≤ 10^5$, $0 ≤ M ≤ 10^5$, $1 ≤ L_i, C_i ≤ 10^4$, $1 ≤ Q ≤ 10^5$, $1 ≤ D ≤ 10^9$.

见题面 Input 部分

见题面 Output 部分