There are $N$ students in your school conveniently labelled from $1$ to $N$. You are person $1$. There are $C$ classes numbered $1$ to $C$, and student $i$ takes $c_i$ different classes. It is guaranteed that every student takes at least one class, although some classes may not have any students.

Two students are able to communicate if and only if they share a class. Additionally, some pairs of people get along more easily than others. Each student has a friend value $v_i$. Then it costs $|v_i-v_j|+K$ for student $i$ to deliver a message to student $j$ where $K$ is fixed for any two students who are able to directly communicate with each other.

The cost required to deliver a message to student $i$ is the sum of the costs from each direct communication. For each $i$, you would like to know the minimum cost required for you, student $1$, to deliver a message to student $i$.

Constraints

For all subtasks:

$1\le v_i\le 1000000$

$1\le c_i$

Subtask 1 [20%]

$1\le N,C\le 400$

$0\le K\le 1000000$

Subtask 2 [30%]

$1\le N,C\le 100000$

$N\le c_1+c_2+\cdots +c_N\le 200000$

$K=0$

Subtask 3 [50%]

$1\le N,C\le 100000$

$N\le c_1+c_2+\cdots +c_N\le 200000$

$0\le K\le 1000000$

Input Specification

The first line contains three space-separated integers, $N$, $C$, and $K$.
The next line contains $N$ space-separated integers, the $i^{\text{th}}$ of which is $v_i$.
The following $N$ lines contain $c_i+1$ space-separated integers. The first number is $c_i$ and the indices of the $c_i$ classes which student $i$ is taking follow.

Output Specification

Output $N$ lines, each containing a single integer. On the $i^{\text{th}}$ line, write the minimum cost required to communicate with student $i$. If it is not possible to communicate with student $i$, print $-1$. Answers are guaranteed to fit within a 64-bit integer.

Sample Input

9 10 7
18 5 6 11 17 19 2 14 5
2 1 7
5 5 2 3 1 10
1 5
2 1 2
2 7 6
1 4
2 3 6
1 10
1 10

Sample Output

0
20
28
14
8
-1
30
36
27