Allison has many electronic devices, such as iMacs, iPods, iPhones, and iPads. Therefore, she plans to buy power strips to charge her devices. After extensive online research, Allison discovered a beautiful and exquisite "Tianyi" brand power strip (as shown in the bottom-left image). Upon seeing this power strip for the first time, Allison was attracted by its exquisite design, so she purchased $n$ power strips of this model at once.

However, problems followed. Allison only has one wall outlet in her home, and she needs to route electricity layer by layer through the connections of the power strips (as shown in the top-right image).

The connection method of the power strips is a tree structure: each power strip's plug is inserted into the socket of another power strip (except for the root node), and the connections of the power strips are not allowed to form cycles.

Each power strip has three wires: a live wire, a neutral wire, and a ground wire. With the increase in the number of power strips and the wear and tear of the wires, the resistance generated by the contact between wires in the circuit has reached a point that cannot be ignored.

How can we describe the tree structure of the power strips and the resistance relationship between the wires? Allison came up with a mathematical model: let $a_i$ represent the ID of the $i$-th power strip, and $f_i$ represent the power strip into which the $i$-th power strip's plug is inserted (i.e., the parent of $a_i$ in the tree). Let 1 represent the live wire, 2 represent the neutral wire, and 3 represent the ground wire. Then the resistance of the entire circuit can be described by $R(a_i, f_i, x, y)$ ($x, y \in \{1, 2, 3\}$), which represents the resistance value between the $x$-wire of $a_i$ and the $y$-wire of $f_i$ (in this mathematical model, Allison assumes that the live wire and neutral wire can also be connected and generate resistance). Below is an example:

Due to the passage of time, the resistance between wires may also change. Now, Allison wants to know the resistance between the $x$-wire of power strip $a_i$ and the $y$-wire of power strip $a_j$ in the power strip tree circuit at the current moment. It is stipulated that the root node of the power strip tree is not plugged into any other power strip, and its ID is 1.

Input

The first line of the input file contains a positive integer $n$, representing the number of power strips.

Next, there are $4(n - 1)$ lines, with every 4 lines forming a block.

The first line of the $i$-th block contains an integer $f_i$, representing that the parent of the power strip with ID $i+1$ is the power strip with ID $f_i$.

The next line contains a $3 \times 3$ matrix $g_{xy}$, where the $x$-th row and $y$-th column represent the reciprocal of the resistance between the $x$-wire of the power strip with ID $i+1$ and the $y$-wire of the power strip with ID $f_i$.

The next line contains an integer $q$, representing the number of operations.

The next $q$ lines each contain several integers.

The first integer is $k$. If $k = 1$, it is followed by four integers $a_i, x_i, a_j, x_j, g$, representing that the resistance value between the $x_i$-wire of power strip $a_i$ and the $x_j$-wire of its parent $a_j$ is changed to the reciprocal of $g$. It is guaranteed that $2 \le a_i \le n$.

If $k = 2$, it is followed by four integers $a_i, x_i, a_j, x_j$, representing a query for the resistance value between the $x_i$-wire of power strip $a_i$ and the $x_j$-wire of power strip $a_j$. It is guaranteed that $a_i \neq a_j$.

Output

For each query, output a real number on a single line representing the resistance between the two wires.

If $\left| \frac{\text{Participant Output} - \text{Standard Output}}{\text{Standard Output}} \right| < 10^{-3}$, the resistance value is considered correct. If all resistance values are correct, you will receive the score for this test case.

Examples

Input 1

3
1
6 7 1 
4 1 8 
8 3 3 
2
7 5 8 
10 5 7 
10 5 5 
10
1 3 1 2 2
1 2 2 3 5
2 3 2 2 2
1 2 3 2 5
1 3 1 2 3
2 1 2 2 3
1 3 2 1 2
2 2 1 1 1
1 2 1 2 5
2 3 1 1 2

Output 1

0.083836
0.095256
0.078828
0.146900

Examples 2

See circuit/circuit.in and circuit/circuit.ans in the participant's directory.

Constraints

For all test data, the input is guaranteed to be a tree. $0 < \text{reciprocal of resistance in input} \le 10$.