Eagle attack

The squirrels and eagles have been at war since ancient times. The Old Squirrel is a master of astrology and has predicted that the eagles will soon attempt one last attack on the Great Tree. According to the Old Squirrel, a number of eagles will fly into the tree at high speed to make the whole tree shake, causing the squirrels to risk falling down.

The tree consists of $N - 1$ branches, which connects $N$ different points that we call nodes (with the tree’s trunk being node $1$). Each branch in the tree thus connects two of these nodes. The Old Squirrel has predicted which of the tree’s $N$ nodes each of the eagles will crash into and at what speed. He wants to know how much each node will shake during the attack to warn all the squirrels about the most dangerous nodes. Unfortunately, the Old Squirrel is not as good at programming as he is at astrology, so he has hired you to calculate how much each node will shake during the attack.

When an eagle crashes with speed $v$ into node $u$, node $u$ begins to shake with strength $v$. The shaking then spreads through the branches that extend from node $u$. When the shaking reaches a certain node, it will spread through all the branches that meet at the new node, except the one the shaking came from. The shaking strength spreads equally along these new branches, so if the shaking had strength $v$ and spreads along $k$ branches, the shaking traveling along the branches will have strength $\frac{v}{k}$. This continues until the shaking eventually reaches nodes that have no other branches than the one from which the shaking came, where the shaking stops spreading.

You can assume that the shaking from a crash spreads through the entire tree and dissipates before the next eagle crashes. For each of the nodes in the tree, the Old Squirrel wants to know the sum of all the shaking strengths that the node will be subjected to.

Input

The first line contains the integer $N$ ($1 \le N \le 100,000$), the number of nodes in the tree. The following $N-1$ lines each contain two integers $a$ and $b$ ($1 \le a, b \le N$), indicating that there is a branch between node $a$ and node $b$.

Next, there is a line with the integer $K$ ($1 \le K \le 100,000$), the number of eagles that will attack. Finally, there are $K$ lines describing the eagles in the order they crash into the tree. Each line contains two integers, the node $u$ ($1 \le u \le N$) where the eagle will crash and the eagle’s speed $v$ ($1 \le v \le 10^9$).

Output

Print one line for each node in the order $1$, $2$, $\dots $ with the sum of all shaking strengths that the node will be subjected to. Your answer is considered correct if it has an absolute or relative error of at most $10^{-5}$.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Sample 2

Figure 1: First eagle.

Figure 2: Second eagle.

The first eagle crashes into node $4$ with a speed of $5$. From node $4$, the shaking spreads only to node $3$ and from node $3$ to both nodes $1$ and $5$. From node $5$, the shaking has nowhere to go, but from node $1$ it spreads to node $2$.

The second eagle crashes into node $3$ with a speed of $6$. From node $3$, the shaking spreads to nodes $1$, $4$, and $5$. The shaking in nodes $4$ and $5$ has nowhere to go, but the shaking in node $1$ spreads to node $2$.

To get the answers, the shaking values for each node are added together, for example, the answer is $2.5+2=4.5$ in node $1$ and $5+6=11$ in node $3$.

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

7
12
9
7

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

4.5
4.5
11
7
4.5