image

Swordon is the leader of the Super Rangers, a group of teenagers with attitude! Each Super Ranger owns a Sword, and one of the Swords is called the Dinosword.

A wire connects two different Swords to each other. There are wires connecting the Swords, such that from any Sword, one can reach any other Sword by following a series of wires.

Swordon can merge two Swords and to a Megasword . When he does, every wire attached to or is instead attached to . Note that all wires connecting and now connect to itself, so they become useless and Swordon removes them.

Swordon can also merge a set of Swords to a Megasword. He does this by merging every pair of Swords in , until one Sword remains. It can be shown the result does not depend on the order Swordon chooses.

Consider the diagram below, which shows an example of merging. The set of Swords colored red are merged to a single Megasword. Observe that after the first pair is merged, there are two wires joining the Megasword and the remaining red Sword. After the second pair of Swords is merged, these two wires join the Megasword to itself, and are removed.

image

The Swords can also transform into Battle Mode. To do this, Swordon divides the Swords into several groups, and merges each group to a single Megasword.

Tita Repulsa, an alien ten times the size of a human, is invading! Swordon needs the Super Rangers to form their Battle Mode. To be effective against Tita Repulsa, the Battle Mode also needs to satisfy the following:

Let be the Dinosword, and the Megasword that replaces . Each Megasword in Battle Mode that is not should be joined to with exactly one wire. There should be no other wires among the Megaswords.

Swordon is only good at wise advice, and not battling aliens. He's not sure which of the Swords is the Dinosword , and instead has a list of possible Dinoswords, . For each possible Dinosword, determine how many ways Swordon can divide the Swords into groups, such that their Battle Mode is effective against Tita Repulsa.

Input Format

The first line contains three integers , , and , the number of Swords, the number of wires connecting the Swords, and the number of possible Dinoswords. The Swords are numbered from to .

The next line contains integers , where each is the number of a possible Dinosword. It is guaranteed that for all .

The next lines each contain two integers and , , representing the th wire joining the Swords numbered and . It is guaranteed that for all .

Constraints

For all subtasks

Subtask 1 (20 points)

Subtask 2 (22 points)

Subtask 3 (38 points)

Subtask 4 (11 points)

Subtask 5 (9 points)

No additional constraints.

Output Format

Print a single line of output containing space-separated numbers, where the th number is the number of ways Swordon can divide the Swords into groups when the Dinosword is Sword number , modulo .

Sample Input 0

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

Sample Output 0

4 6 6

Explanation 0

There are Swords and wires connecting these Swords, like so: 1-2-3-4.

image

If the Dinosword is , there are distinct ways the Swords can be grouped, such that their Battle Mode is effective:

The following ways are invalid:

is not valid, as there would be a wire between the Megasword formed from and the Megasword formed from , neither of which is the Megasword that replaces the Dinosword . Also, the Megasword that replaces would not be joined by any wires to the Megasword that replaces the Dinosword .

is not valid, as there would be two wires between the Megasword formed from and the Megasword formed from , neither of which is the Megasword that replaces the Dinosword . Also, the Megasword that replaces would not be joined by any wires to the Megasword that replaces the Dinosword .

is not valid, as there would be multiple wires joining the Megasword formed from and the Megasword formed from .

If the Dinosword is , there are distinct ways:

If the Dinosword is , there are also distinct ways, not shown here.

Sample Input 1

4 3 6
4 3 2 1 4 3
1 2
1 3
1 4

Sample Output 1

5 5 5 8 5 5

Sample Input 2

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

Sample Output 2

1 1 1 1 1 1

Explanation 2

Regardless of which Sword is the Dinosword, there is only one way to group the Swords: that is to merge all of them into one Megasword.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score