King Gruff

Interview

Time limit2sMemory limit256 MB

Summary

For each query, sum the shutdown costs of roads lying on some A to B path whose total length is at most D.

Level: Medium6 of 10
Topics: Shortest path, Sorting, Prefix sum
Solved: No attempts yet

Problem

King Gruff rules N cities connected by M directed roads. Road i goes from Xi to Yi with length Li and shutdown cost Ci. For distance limit D, he shuts down every road that belongs to at least one path from A to B with total length at most D. Answer Q queries, each with a value Di, giving the total shutdown cost.

Input

The first line has N, M, A, and B. Each of the next M lines has Xi, Yi, Li, and Ci. The next line has Q, followed by Q lines each with Di.

Output

Print Q lines, the total shutdown cost for each Di.

Examples2

Example 1

Input

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

Expected output

Example 2

Input

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

Expected output