Toy Distribution for Children

There are n children. Some children play with toys alone while others play in pairs. You are given m pairs among these children. When a pair plays together, they must receive different toys. In addition, the remaining n - 2m children (if any) play alone, so there is no restriction for them.

There are k types of toys available. The distribution scheme must ensure that in each pair the two children get different toy types.

The total number of valid distribution schemes is:

[ \text{ways} = k^{(n-2m)} \times (k \times (k-1))^m ]

You are given z queries. In each query, n, m and the corresponding pairs remain the same, but the value of k changes. For each query output the number of valid distribution schemes.

inputFormat

The first line contains three integers: n (total number of children), m (number of pairs), and z (number of queries).

The next m lines each contain two integers representing the indices of the children that form a pair. (Note that the pairs are fixed and affect the value of m only.)

The following z lines each contain a single integer k (number of toy types available).

outputFormat

For each query, output a single integer representing the number of valid toy distribution schemes. Each answer should be printed on a new line.

sample

4 1 2
1 2
3
1

54
0