Allison possède de très nombreux appareils électroniques, tels qu'un iMac, un iPod, un iPhone et un iPad. Elle prévoit donc d'acheter des multiprises pour les recharger. Après de nombreuses recherches sur Internet, Allison a découvert une belle multiprise raffinée de marque Tianyi (sur l'image en bas à gauche). Dès le premier regard, elle a été séduite par sa jolie forme et en a acheté $n$ du même modèle en une seule fois.

Mais un problème s'est alors posé : Allison ne dispose que d'une prise murale chez elle. Elle doit brancher les multiprises les unes aux autres pour distribuer l'électricité de proche en proche (comme sur l'image en haut à droite).

Les branchements des multiprises forment un arbre : la fiche de chaque multiprise est branchée dans une prise d'une autre multiprise (sauf pour la racine), et les branchements ne peuvent former aucun cycle.

Chaque multiprise comporte trois conducteurs : la phase, le neutre et la terre. Avec l'augmentation du nombre de multiprises et l'usure des conducteurs, les résistances dues aux contacts entre les conducteurs du circuit ne peuvent plus être négligées.

Comment décrire l'arbre des multiprises et les résistances entre les conducteurs ? Allison a imaginé un modèle mathématique : $a_i$ désigne le numéro de la $i$-ème multiprise et $f_i$ la multiprise à laquelle sa fiche est branchée (c'est-à-dire le parent de $a_i$ dans l'arbre). Les numéros $1$, $2$ et $3$ désignent respectivement la phase, le neutre et la terre. Les résistances du circuit peuvent alors être décrites par $R(a_i,f_i,x,y)$ ($x,y\in\{1,2,3\}$), qui représente la résistance entre le conducteur $x$ de $a_i$ et le conducteur $y$ de $f_i$. (Dans ce modèle mathématique, Allison considère que la phase et le neutre peuvent aussi être reliés et produire une résistance.) Voici un exemple :

Les résistances entre conducteurs peuvent aussi évoluer au fil du temps. Allison souhaite maintenant connaître, à l'instant présent, la résistance entre le conducteur $x$ de la multiprise $a_i$ et le conducteur $y$ de la multiprise $a_j$ dans ce circuit en arbre. La multiprise racine n'est branchée à aucune autre multiprise et porte le numéro $1$.

Entrée

La première ligne du fichier d'entrée circuit.in contient un entier strictement positif $n$, le nombre de multiprises.

Les $4(n-1)$ lignes suivantes sont divisées en blocs de $4$ lignes.

La première ligne du bloc $i$ contient un entier $f_i$, indiquant que le parent de la multiprise numéro $i+1$ est la multiprise $f_i$.

Vient ensuite une matrice $g_{xy}$ de dimensions $3\times3$. L'élément à la ligne $x$ et à la colonne $y$ représente l'inverse de la résistance entre le conducteur $x$ de la multiprise numéro $i+1$ et le conducteur $y$ de $f_i$.

Vient ensuite un entier $q$, le nombre d'opérations.

Les $q$ lignes suivantes contiennent chacune plusieurs entiers.

Le premier entier est $k$. Si $k=1$, il est suivi de quatre entiers $a_i,x_i,x_j,g$, indiquant que la résistance entre le conducteur $x_i$ de la multiprise $a_i$ et le conducteur $x_j$ de son parent $f_i$ doit devenir l'inverse de $g$. Il est garanti que $2\le a_i\le n$.

Si $k=2$, il est suivi de quatre entiers $a_i,x_i,a_j,x_j$, demandant la résistance entre le conducteur $x_i$ de la multiprise $a_i$ et le conducteur $x_j$ de la multiprise $a_j$. Il est garanti que $a_i\ne a_j$.

Sortie

Le fichier de sortie est circuit.out.

Pour chaque requête, affichez sur une ligne un réel représentant la résistance entre les deux conducteurs.

Une résistance est considérée comme correcte si

$$ \left|\frac{\text{sortie du participant}-\text{sortie de référence}}{\text{sortie de référence}}\right|<10^{-3}. $$

Si toutes les résistances sont correctes, vous obtenez les points du test.

Exemples

Entrée 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

Sortie 1

0.083836
0.095256
0.078828
0.146900

Entrée et sortie 2

Voir les fichiers circuit/circuit.in et circuit/circuit.ans dans le répertoire du participant.

Contraintes

Pour tous les tests, l'entrée est garantie de former un arbre. Les inverses des résistances dans l'entrée sont strictement supérieurs à $0$ et inférieurs ou égaux à $10$.