Description

Given a tree-structured electrical network, each edge in the tree has a resistor $R_i$ with a resistance of $10000\,\Omega$. The following figure shows a tree-structured circuit with 4 nodes:

All leaf nodes in the tree (nodes with degree 1 are called leaf nodes) are grounded, and each grounding wire has a $10000\,\Omega$ resistor attached. The final network is shown in the figure below:

There are two types of operations:

• C u v w: Connect a power source in series on the edge $\langle u, v \rangle$. The power source has a voltage of $w$ volts and is located near node $u$ (as shown in the figure below), with its negative terminal pointing towards $u$. Note that multiple power sources can be connected in series on the same edge.

• Q u: Query the current voltage at node $u$. This voltage is defined as the voltage relative to ground.

After performing the C 2 4 5 operation on the network above, the network becomes:

The voltage at each node at this time is marked in the figure above.

Input

The first line contains two integers $N$ and $M$, representing the number of nodes in the tree and the number of operations, respectively. The next $N-1$ lines each contain two integers $u, v$, representing an edge connecting nodes $u$ and $v$. Each such edge contains exactly one resistor.

The next $M$ lines each contain a command, the format of which is described in the problem description.

Output

For each Q command, output a single number representing the voltage at that node. You may output any number of decimal places, as long as your answer differs from the standard answer by no more than $10^{-3}$.

Examples

Input 1

4 3
1 2
2 3
2 4
Q 2
C 2 4 5
Q 2

Output 1

0.0000000000
-1.6666666666

Note

For the first query, since there are no power sources in the original graph, there is no current, and the voltages at all points are equal (otherwise, if $U_i > U_j$, there would be a current flowing from $i$ to $j$, which contradicts the absence of power sources), all equal to the ground voltage $0\,\text{V}$.

After adding a $5\,\text{V}$ power source to $\langle 2, 4 \rangle$, the new graph is as described in the problem.

After simplification, it can be seen that the new graph is in the form of a series connection of (power source, $R_2 + 10000$, parallel($R_1 + 10000$, $R_3 + 10000$)). From this, the total resistance of the new graph can be obtained: $R_2 + 10000 + 1 / (1 / (R_3 + 10000) + 1 / (R_1 + 10000)) = 30000\,\Omega$.

Therefore, the current flowing through node 4 is $5 / 30000\,\text{A}$, so $U_4 = 5 / 3\,\text{V}$. $U_2 = U_4 + R_2 \cdot I - 5 = -5 / 3\,\text{V}$. Since $U_1$ and $U_3$ are symmetric in form, by the voltage divider rule, $U_1 = U_3 = U_2 \cdot 10000 / (10000 + 10000) = -5 / 6\,\text{V}$.

Subtasks

• 30% of the data: $N, M \le 30$
• 60% of the data: $N, M \le 3000$
• 100% of the data: $3 \le N, M \le 50000$, $1 \le u, v \le n$, $1 \le w \le 10$, and the length of the longest chain in the tree does not exceed 50.