Problem D
Metro Mapping

Mario is currently visiting the Metro Kingdom. Unsurprisingly, he is looking forward to taking the metro to travel across the kingdom. The metro has $M$ stations and $N$ train lines. Each line $i$ passes through a subset $S_ i$ of the $M$ stations, and when Mario is riding on a line $i$, he can travel forward or backward between adjacent stations of the line. When passing through a station $x$, Mario can also switch from one line to another if both lines contain $x$. Today, he’s aiming to get from station $1$ (his hotel) to station $M$ (the city’s town hall).

Traveling between two adjacent stations on the same line takes $A$ units of time. However, switching lines takes $B$ units of time. $A$ stays constant, while $B$ varies depending on how much Mario wants to exert himself walking through the station.

Note that when Mario starts his journey from his hotel, he can choose to start on any line that passes through station $1$. This does not count as a line change. He may also arrive at station $M$ on any line.

Mario always takes an optimal (shortest) route to the city hall. Given $T$ different values of $B$, what is the time it takes for Mario to get to the town hall for each value of $B$?

For example, in the first sample case, if the time required to switch lines is $B = 2$, then the optimal path is to start at line $1$ and travel forward from station $1$ to station $2$ on line $1$. From there, Mario switches to line $2$ and travels backward from station $2$ to station $4$ on line $2$. The total time taken is $5 + 2 + 5 = 12$; this is the shortest possible time to reach station $4$ with $B=2$.

Input

The first line of input contains two space-separated integers $M \: (1 \leq M \leq 100)$ and $N \: (1 \leq N \leq 10)$ representing the number of stations and the number of lines respectively.

The second line of input contains a single integer $A \: (1 \leq A \leq 500\, 000)$ representing the amount of time it takes to travel forward or backward between adjacent stations on the same line.

Then $N$ lines follow describing the stations on each line. The $i$th line starts with an integer $|S_ i| \: (1 \leq |S_ i| \leq M)$, the number of stations that line $i$ passes through. This is followed by another $|S_ i|$ distinct space-separated integers $a_1, a_2, \ldots , a_{|S_ i|}$ ($1 \leq a_ i \leq M$) representing all the train stations on line i. Stations $a_{j}$ and $a_{k}$ are considered adjacent on line $i$ if $|j-k|=1$.

Another line follows containing a single integer $T \: (1 \leq T \leq 100\, 000)$ indicating the number of values of $B$ considered.

Finally, $T$ lines follow containing integers $B_1, \ldots , B_ T \: (0 \leq B_ i \leq 500\, 000)$, one value per line. These numbers represent each value of $B$ considered (i.e. possible amounts of time Mario takes to switch between metro lines).

It is guaranteed that there is always a way to travel from station $1$ to station $M$.

Output

Output $T$ lines: on the $i$th line output the shortest amount of time required to go from the hotel to the town hall with $B = B_ i$.

4 2
5
4 1 2 3 4
2 4 2
3
0
2
6

10
12
15

10 3
2
4 1 2 3 4
5 6 2 5 9 10
4 2 9 8 7
2
0
5

6
13