Est is a super cute sword spirit that belongs to Kamito. One day, she goes for a walk with him in a spirit forest in Astral Zero. Est quickly realizes that this forest has many clearings and paths, and the clearings and paths actually form a tree structure.

There are clearings numbered from to and paths in the spirit forest, and between every pair of clearings there is a unique simple path. In every clearing there may be a demon spirit, which Est will immediately defeat as she is far superior than these lowly demon spirits. Est is eager to defeat some demon spirits, but there is a problem: she doesn't know which clearing she is in right now (although she memorized the layout of the forest). For lack of a better option, Est decides to just keep moving from her current location **without walking over the same path more than once** and fight every demon spirit she meets along the way. Est may decide to stop at a clearing at any time during this journey. The path will visit at least two clearings, including the one Est starts at.

A path between clearings and is considered **good** if for two parameters and there are there are at least demon spirits and at most demon spirits on the simple path between and . Est will enjoy herself the most if the path she chooses is a **good** path. Thus, she has questions: given parameters and , what is the probability that the path she takes is a good path?

Est is quite kind, and as such, she does not want you to deal with incredibly small real numbers. Therefore, if is the probability, you should output . This comes from the fact that the probability of choosing a **good** path is the number of **good** paths divided by the total number of paths. Since Est does not know where she is initially, we should assume each clearing has a chance of being Est's initial clearing. Since Est's will cannot be predicted by mere humans, we should also assume each clearing **that is not the initial clearing** has a chance of being chosen as the final clearing where Est stops. In other words, you will just need to output the **number of distinct good paths in the spirit forest** for every and Est asks you. In particular, **a path is considered distinct from another path if one path visits a clearing that the other path doesn't**. Therefore, there are distinct paths in total.

**Note:** Demon spirits don't move from their initial clearings.

#### Input Specification

The first line of input will have .

The second line of input will have space-separated digits, either or . If and only if the number if , the clearing has a demon spirit.

The next lines describe the spirit forest. Each line in the form which means that clearings and are directly connected.

The line will have .

The next lines each have and , separated by a single space.

#### Output Specification

There should be lines of output, the answers to Est's questions. You should output the answers to Est's questions in the order that they are given.

#### Constraints

There will be a number of subtasks for this problem:

Test Case Batch | Points (%) | Constraints |
---|---|---|

1 | 1 | |

2 | 2 | |

3 | 2 | |

4 | 10 | |

5 | 15 | |

6 | 15 | |

7 | 25 | |

8 | 30 |

#### Sample Input

```
8
0 1 1 1 1 0 0 1
2 1
3 1
4 1
5 4
6 5
7 4
8 4
3
0 8
1 2
3 3
```

#### Sample Output

```
28
20
8
```

## Comments

This comment is hidden due to too much negative feedback. Click here to view it.

It is mentioned in the question that demon spirits reside on paths, and a good path is a path where the demon spirits on the path are within the condition a < demons < b. However, later on it says that demon spirits dont move from their

clearings. How do I know how many demon spirits are on a given path?Real talk I think you should start with some easier problems like Arrow.