Water in a Tree

There is a tree consist of $N$ nodes and $N-1$ edges. The $i^{th}$ node contains $S_i$ liters of water with a temperature of $T_i$ degrees. The temperature of water in each node remains unchanged until they are mixed with more water.

You have to perform $Q$ queries of two types on the tree:

$Type$$1:$ You will be given a path from node $U$ to node $V$. What will be the temperature of the water if we mix all the water of all nodes in the path from node $U$ to node $V$. Also, you have to find the total number of liters of water in that path. Properties of the tree will remain unchanged during this type of query. When we mix water from two different nodes $a$ and $b$. The following rule will be applied:

$T_a × S_a + T_b × S_b = T_c × (S_a+S_b)$,

where $T_a$ and $T_b$ are the temperatures of water in node $a$ and node $b$ respectively. $S_a$ and $S_b$ are the numbers of the liter of water in node $a$ and node $b$. $T_c$ is the new temperature of the water after mixing.

$Type$$2:$ Update the volume and temperature of water in node $U$.

Input

The First line contains two numbers $N$ and $Q$ $(3 \leq N, Q \leq 10^5)$. Here, $N$ is the number of nodes and $Q$ is the number of queries respectively.

Each of the next $N-1$ lines consists of two integers $U$ and $V$$(1 \leq U, V \leq N, U\neq V)$ denoting there is an edge between nodes numbered $U$ and $V$.

$N$ line follows. For each $i$ from $1$ to $N$, $i^{th}$ line will have two integers $T_i$ and $S_i$ $(1\leq T_i, S_i \leq 10^3)$. $T_i$ is the temperature of the water in the $i^{th}$ node and $S_i$ is the volume of water in liters of $i^{th}$ node.

Following $Q$ lines describe a query at each line.

$Type$ $1:$ 1 $U$ $V$ $(1 \leq U, V \leq N)$.
$Type$ $2:$ 2 $i$ $T_i$ $S_i$ $(1 \leq T_i, S_i \leq 10^3)$ where $T_i$ and $S_i$ is integer numbers denoting new temparature and water volume respectively.

For type 2 queries, change the temperature of water of $i^{th}$ node to $T_i$ and volume of water to $S_i$ liters.

For 40 Points: Every constraint is less than or equal to $10^3$.
For 100 Points: Original constraints.

Output

For each of the Type 1 queries, print two real numbers ${X }$ and $Y$. $X$ is the average temperature and $Y$ is the total volume of water if we mix the waters of all nodes of the path from node $U$ to node $V$.

The answer will be considered correct if its relative or absolute error doesn't exceed $10^{-4}$.

Sample

5 4
1 2
2 3
2 4
1 5
30 2
80 1
70 2
50 3
100 1
1 2 5
1 5 3
2 2 70 2
1 5 3

60.00000 4.00000
63.33333 6.00000
62.85714 7.00000