Consider a graph organized into a grid of nodes and edges, where each row has ~N~ nodes and there is an infinite number of rows. In this graph, node ~(x,y)~ refers to the ~y~-th node in the ~x~-th row. A given bipartition function will add ~M~ directed edges per row, each of which joins the ~a_i~-th node in that row (row ~x~) to the ~b_i~-th node in the row immediately after (row ~x+1~).

Someone who lives on this graph is interested in travelling to various rows. He can only start his trip from some node in row ~1~, and sets the condition that, in order to reach any destination node, he must start his travels from node ~(1,y)~ such that ~y~ is minimized. Formally, he will not travel from node ~(1,y)~ to any destination ~(r,s)~ if there exists at least one path from node ~(1,y')~ to ~(r,s)~, and ~y' < y~. To plan his trip to a desired row, he would like to reflect on how many distinct sequences of nodes he could travel through in order to reach his destination.

Help him by answering ~Q~ queries:

For every node in row ~q_i~, how many distinct ways modulo ~1\,000\,000\,007~ ~(= 10^9+7)~ are there to travel from the desired node in row ~1~ to this node?

Two ways are considered distinct if they pass through different sequences of nodes. Note that in some rows, the desired starting point (in row ~1~) may be different for different nodes.

Input Specification

On the first line, read the three integers ~N~, ~M~, and ~Q~.

On each of the next ~M~ lines, read the two integers ~a_i~ and ~b_i~. ~1 \le a_i,b_i \le N~

On each of the next ~Q~ lines, read one integer ~q_i~.

Output Specification

For each query, print one line containing the answers for nodes ~1~ to ~N~ in row ~q_i~, with each answer separated by a single space.

Subtasks and Constraints

For all subtasks:

~1 \le N, Q \le 100~

~M \le N^2~

~2 \le q_i \le 10^{13}~

Subtask 1 [5%]

~N \le 10~

~q_i \le 10~

Subtask 2 [10%]

~q_i \le 1000~

Subtask 3 [35%]

~Q = 1~

Subtask 4 [50%]

No additional constraints.

Sample Input 1

4 5 3
1 2
2 1
3 3
3 4
4 4
2
3
4

Sample Output 1

1 1 1 1
1 1 1 2
1 1 1 3

Explanation for Sample 1

The graph is as illustrated below.

For node ~(3,4)~, the two distinct ways are to travel from ~(1,3)~ to ~(2,3)~ and from ~(1,3)~ to ~(2,4)~ before reaching it. Note that it is also reachable from ~(1,4)~, but that is irrelevant, as ~(1,3)~ is a lower numbered node in the first row.

For node ~(4,4)~, the three ways are ( ~(1,3) \to (2,3) \to (3,4) \to (4,4)~ ), ( ~(1,3) \to (2,3) \to (3,3) \to (4,4)~ ), and ( ~(1,3) \to (2,4) \to (3,4) \to (4,4)~ ).

Sample Input 2

3 5 2
1 1
1 2
2 2
2 3
3 1
3
4

Sample Output 2

1 2 1
2 3 2