马里奥目前正在访问地铁王国。不出所料，他正期待着乘坐地铁环游这个王国。地铁系统拥有 $M$ 个车站和 $N$ 条地铁线路。每条线路 $i$ 穿过 $M$ 个车站中的一个子集 $S_i$。当马里奥乘坐线路 $i$ 时，他可以在该线路的相邻车站之间向前或向后旅行。当经过车站 $x$ 时，如果两条线路都包含 $x$，马里奥也可以从一条线路换乘到另一条线路。今天，他的目标是从 1 号车站（他的酒店）前往 $M$ 号车站（市政厅）。

在同一条线路上，在两个相邻车站之间旅行需要花费 $A$ 个单位的时间。然而，换乘线路需要花费 $B$ 个单位的时间。$A$ 保持不变，而 $B$ 则取决于马里奥想在车站内步行付出多少努力。

请注意，当马里奥从酒店开始他的旅程时，他可以选择从经过 1 号车站的任何线路开始。这不计入线路换乘。他也可以乘坐任何线路到达 $M$ 号车站。

马里奥总是选择前往市政厅的最优（最短）路线。给定 $T$ 个不同的 $B$ 值，对于每个 $B$ 值，马里奥到达市政厅所需的时间是多少？

例如，在第一个样例中，如果换乘线路所需的时间为 $B = 2$，那么最优路径是：从线路 1 开始，在线路 1 上从 1 号车站向前旅行到 2 号车站。从那里，马里奥换乘到线路 2，并在线路 2 上从 2 号车站向后旅行到 4 号车站。总共花费的时间为 $5 + 2 + 5 = 12$；这是在 $B = 2$ 时到达 4 号车站的最短可能时间。

输入格式

输入的第一行包含两个空格分隔的整数 $M$（$1 \le M \le 100$）和 $N$（$1 \le N \le 10$），分别代表车站数量和线路数量。

第二行包含一个整数 $A$（$1 \le A \le 500\,000$），代表在同一条线路上相邻车站之间向前或向后旅行所需的时间。

接下来的 $N$ 行描述了每条线路上的车站。第 $i$ 行以一个整数 $|S_i|$（$1 \le |S_i| \le M$）开始，即线路 $i$ 经过的车站数量。紧接着是 $|S_i|$ 个不同的空格分隔的整数 $a_1, a_2, \dots, a_{|S_i|}$（$1 \le a_i \le M$），代表线路 $i$ 上的所有地铁站。如果 $|j - k| = 1$，则车站 $a_j$ 和 $a_k$ 在线路 $i$ 上被认为是相邻的。

接下来的一行包含一个整数 $T$（$1 \le T \le 100\,000$），表示考虑的 $B$ 值的数量。

最后 $T$ 行，每行包含一个整数 $B_1, \dots, B_T$（$0 \le B_i \le 500\,000$）。这些数字代表每个考虑的 $B$ 值（即马里奥在地铁线路之间换乘可能需要的时间）。

保证总是存在一条从 1 号车站到 $M$ 号车站的路线。

输出格式

输出 $T$ 行：在第 $i$ 行输出当 $B = B_i$ 时，从酒店到市政厅所需的最短时间。

样例

输入样例 1

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

输出样例 1

10
12
15

输入样例 2

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

输出样例 2

6
13