Allison tiene muchos dispositivos electrónicos, como iMac, iPod, iPhone e iPad. Por ello, piensa comprar regletas para cargarlos. Tras investigar mucho por Internet, Allison encontró una regleta bonita y elegante de la marca 天翼 (como se muestra abajo a la izquierda). En cuanto la vio, quedó cautivada por su diseño y compró de una sola vez $n$ regletas de este modelo.

Sin embargo, surgió un problema: en casa de Allison solo hay una toma de corriente, por lo que necesita conectar las regletas para distribuir la electricidad por varios niveles (como se muestra arriba a la derecha).

Las conexiones entre las regletas forman un árbol: el enchufe de cada regleta se conecta a una toma de otra regleta (salvo la raíz), y las conexiones no pueden formar ciclos.

Cada regleta tiene tres conductores: fase, neutro y tierra. Con el aumento del número de regletas y el desgaste de los conductores, la resistencia producida por el contacto entre los conductores del circuito ya no puede ignorarse.

¿Cómo describir la estructura de árbol de las regletas y las resistencias entre sus conductores? Allison ideó un modelo matemático: $a_i$ representa el número de la regleta $i$, y $f_i$ representa la regleta a la que se enchufa la regleta $i$ (es decir, el padre de $a_i$ en el árbol). Los números $1$, $2$ y $3$ representan la fase, el neutro y la tierra, respectivamente. Las resistencias de todo el circuito pueden describirse mediante $R(a_i,f_i,x,y)$, con $x,y\in\{1,2,3\}$, que representa la resistencia entre el conductor $x$ de $a_i$ y el conductor $y$ de $f_i$. (En este modelo matemático, Allison considera que la fase y el neutro también pueden estar conectados y producir resistencia). A continuación se muestra un ejemplo:

Con el paso del tiempo, las resistencias entre los conductores pueden cambiar. Ahora Allison quiere conocer, en el circuito de regletas con forma de árbol, la resistencia actual entre el conductor $x$ de la regleta $a_i$ y el conductor $y$ de la regleta $a_j$. Se establece que la regleta raíz del árbol no se enchufa a ninguna otra regleta y tiene el número $1$.

Entrada

La primera línea del archivo de entrada circuit.in contiene un entero positivo $n$, que indica el número de regletas.

A continuación hay $4(n-1)$ líneas, agrupadas en bloques de cuatro líneas.

La primera línea del bloque $i$ contiene un entero $f_i$, que indica que el padre de la regleta de número $i+1$ es la regleta $f_i$.

Después se da una matriz $g_{xy}$ de tamaño $3\times3$. El elemento de la fila $x$ y la columna $y$ es el recíproco de la resistencia entre el conductor $x$ de la regleta $i+1$ y el conductor $y$ de $f_i$.

A continuación se da un entero $q$, que indica que hay $q$ operaciones.

Las siguientes $q$ líneas contienen varios enteros cada una.

El primer entero es $k$. Si $k=1$, a continuación hay cuatro enteros $a_i,x_i,x_j,g$, que indican que la resistencia entre el conductor $x_i$ de la regleta $a_i$ y el conductor $x_j$ de su padre $f_i$ se cambia al recíproco de $g$. Se garantiza que $2\le a_i\le n$.

Si $k=2$, a continuación hay cuatro enteros $a_i,x_i,a_j,x_j$, que indican una consulta sobre la resistencia entre el conductor $x_i$ de la regleta $a_i$ y el conductor $x_j$ de la regleta $a_j$. Se garantiza que $a_i\ne a_j$.

Salida

El archivo de salida es circuit.out.

Para cada consulta, escribe en una línea un número real que indique la resistencia entre los dos conductores.

Si $\left|\frac{\text{salida del participante}-\text{salida de referencia}}{\text{salida de referencia}}\right|<10^{-3}$, el valor de la resistencia se considera correcto. Si todos los valores de resistencia son correctos, se obtienen los puntos del caso de prueba.

Ejemplos

Entrada 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

Salida 1

0.083836
0.095256
0.078828
0.146900

Ejemplo 2

Consulta los archivos circuit/circuit.in y circuit/circuit.ans del directorio del participante.

Restricciones

Para todos los datos de prueba, se garantiza que la entrada describe un árbol. El recíproco de cada resistencia de la entrada satisface $0<\text{recíproco de la resistencia}\le10$.