Allison possui muitos aparelhos eletrônicos, como iMac, iPod, iPhone e iPad. Por isso, ela pretende comprar réguas de tomadas para carregá-los. Após uma extensa pesquisa na Internet, Allison encontrou uma bela e delicada régua de tomadas da marca Tianyi (mostrada na imagem inferior à esquerda). Ao vê-la pela primeira vez, Allison ficou encantada com seu belo formato e comprou de uma só vez $n$ réguas desse modelo.

Mas surgiu um problema: Allison tem apenas uma tomada em casa, e precisa conectar as réguas para distribuir a eletricidade em vários níveis (como na imagem superior à direita).

As conexões entre as réguas formam uma árvore: o plugue de cada régua é conectado a uma tomada de outra régua, exceto no caso da raiz. As conexões não podem formar ciclos.

Cada régua possui três condutores: fase, neutro e terra. Com o aumento do número de réguas e o desgaste dos condutores, a resistência produzida pelo contato entre os condutores do circuito já não pode ser ignorada.

Como descrever a estrutura em árvore das réguas e as resistências entre seus condutores? Allison elaborou um modelo matemático: $a_i$ representa o identificador da régua $i$, e $f_i$ representa a régua na qual o plugue da régua $i$ está conectado (isto é, o pai de $a_i$ na árvore). Os números $1$, $2$ e $3$ representam fase, neutro e terra, respectivamente. Assim, as resistências do circuito inteiro podem ser descritas por $R(a_i,f_i,x,y)$ ($x,y\in\{1,2,3\}$), que representa a resistência entre o condutor $x$ de $a_i$ e o condutor $y$ de $f_i$. (Nesse modelo matemático, Allison considera que fase e neutro também podem estar conectados e produzir resistência.) Veja um exemplo abaixo:

Com o passar do tempo, as resistências entre os condutores também podem mudar. Agora, Allison quer saber a resistência, no instante atual, entre o condutor $x$ da régua $a_i$ e o condutor $y$ da régua $a_j$ no circuito em árvore. A régua que é a raiz da árvore não se conecta a nenhuma outra régua e tem identificador $1$.

Entrada

A primeira linha do arquivo de entrada circuit.in contém um inteiro positivo $n$, o número de réguas.

As próximas $4(n-1)$ linhas são divididas em blocos de $4$ linhas.

A primeira linha do bloco $i$ contém um inteiro $f_i$, indicando que o pai da régua com identificador $i+1$ é a régua $f_i$.

Em seguida vem uma matriz $3\times3$, $g_{xy}$. A entrada na linha $x$ e coluna $y$ representa o inverso da resistência entre o condutor $x$ da régua com identificador $i+1$ e o condutor $y$ de $f_i$.

Em seguida vem um inteiro $q$, indicando o número de operações.

As próximas $q$ linhas contêm alguns inteiros em cada linha.

O primeiro inteiro é $k$. Se $k=1$, seguem quatro inteiros $a_i,x_i,x_j,g$, indicando que a resistência entre o condutor $x_i$ da régua $a_i$ e o condutor $x_j$ de seu pai $f_i$ deve ser alterada para o inverso de $g$. É garantido que $2\le a_i\le n$.

Se $k=2$, seguem quatro inteiros $a_i,x_i,a_j,x_j$, que representam uma consulta à resistência entre o condutor $x_i$ da régua $a_i$ e o condutor $x_j$ da régua $a_j$. É garantido que $a_i\ne a_j$.

Saída

O arquivo de saída é circuit.out.

Para cada consulta, escreva uma linha com um número real que representa a resistência entre os dois condutores.

Se $\left|\frac{\text{saída do participante}-\text{saída padrão}}{\text{saída padrão}}\right|<10^{-3}$, o valor da resistência é considerado correto. Se todos os valores de resistência estiverem corretos, você receberá a pontuação desse caso de teste.

Exemplos

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

Saída 1

0.083836
0.095256
0.078828
0.146900

Entrada e saída 2

Veja circuit/circuit.in e circuit/circuit.ans no diretório do participante.

Restrições e convenções

Para todos os dados de teste, é garantido que a entrada representa uma árvore. O inverso de cada resistência na entrada é maior que $0$ e menor ou igual a $10$.