Unfortunately, it turns out that a lot of the shows you've been watching this season haven't really lived up to their hype. To vent your frustration, you've decided to spend the weekend jumping in a tree instead.
The tree you're jumping in is rooted at node with
nodes connected by
edges, the
-th edge connecting nodes
and
with a length of
. Each node
has
values
and
.
You may jump from node to node
if
is a descendant of
and
, with a danger factor of
where
is the length of the shortest path from
to
.
For each node from
to
, find the minimum danger factor of a direct jump from some node to node
or determine that it is impossible to jump to this node.
Constraints
Subtask 1 [30%]
and
for all
.
Subtask 2 [70%]
No additional constraints.
Input Specification
The first line contains an integer .
The second line contains integers
.
The third line contains integers
.
The next lines each contain
integers
,
, and
.
Output Specification
Output lines, the
-th line containing the minimum danger factor of a direct jump from some node to node
or
Unreachable
if it is impossible to jump to this node. Your output will be considered correct if the absolute or relative error of each numerical value does not exceed .
Sample Input
7
11 8 7 2 6 3 9
2 1 1 5 4 3 13
2 4 3
1 2 3
7 1 4
3 6 6
2 3 2
5 3 1
Sample Output
0.300000000000
0.285714285714
1.000000000000
0.333333333333
1.375000000000
Unreachable
Explanation
For node , it is best to jump from node
to node
with a danger factor of
.
For node , it is best to jump from node
to node
with a danger factor of
.
For node , it is best to jump from node
to node
with a danger factor of
.
For node , it is best to jump from node
to node
with a danger factor of
.
For node , it is best to jump from node
to node
with a danger factor of
.
For node , it is impossible to jump to this node.
Comments