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 *N* clearings numbered from 1 to *N* and *N-1* 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 *i* and *j* *(i < j)* is considered **good** if for two parameters *a* and *b (0 ≤ a ≤ b ≤ N)* there are at least *a* demon spirits and at most *b* demon spirits on the simple path between *i* and *j*. Est will enjoy herself the most if the path she chooses is a **good** path. Thus, she has *Q* questions: given parameters *a* and *b*, 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 *p* is the probability, you should output *p·N·(N-1)/2*. 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 *1/N* 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 *1/(N-1)* 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 *a* and *b* 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 * N·(N-1)/2* distinct paths in total.

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

The first line of input will have *N*.

The second line of input will have *N* space-separated digits, either 0 or 1. If and only if the *i ^{th}* number is 1, the

*i*clearing has a demon spirit.

^{th}
The next *N-1* lines describe the spirit forest. Each line in the form *u v* which means the clearings *u* and *v* are directly connected.

The *(N+2) ^{th}* line with have

*Q.*

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

There should be *Q* 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.

- 2 ≤
*N*≤ 100000 - 1 ≤
*Q*≤ 200000

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

28 20 8

- 8s
- 256MB

**Problem source:** DMOJ