There are students in your school conveniently labelled from to . You are person . There are classes numbered to , and student takes 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 . Then it costs for student to deliver a message to student where is fixed for any two students who are able to directly communicate with each other.
The cost required to deliver a message to student is the sum of the costs from each direct communication. For each , you would like to know the minimum cost required for you, student , to deliver a message to student .
For all subtasks:
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
The first line contains three space-separated integers, , , and .
The next line contains space-separated integers, the of which is .
The following lines contain space-separated integers. The first number is and the indices of the classes which student is taking follow.
Output lines, each containing a single integer. On the line, write the minimum cost required to communicate with student . If it is not possible to communicate with student , print . Answers are guaranteed to fit within a 64-bit integer.
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
0 20 28 14 8 -1 30 36 27