Allison ma bardzo wiele urządzeń elektronicznych, takich jak iMac, iPod, iPhone i iPad. Postanowiła więc kupić listwy zasilające, aby je ładować. Po obszernych poszukiwaniach w Internecie znalazła piękną i pomysłową listwę marki Tianyi (pokazaną na ilustracji po lewej poniżej). Już na pierwszy rzut oka zachwycił ją jej wygląd, więc od razu kupiła $n$ listew tego modelu.

Pojawił się jednak problem: w domu Allison jest tylko jedno gniazdko. Musi ona przekazywać zasilanie przez kolejne poziomy połączonych listew (jak na ilustracji powyżej po prawej).

Połączenia listew tworzą drzewo: wtyczka każdej listwy, z wyjątkiem korzenia, jest podłączona do gniazda innej listwy. Połączenia nie mogą tworzyć cyklu.

Każda listwa ma trzy przewody: fazowy, neutralny i ochronny. Wraz ze wzrostem liczby listew i zużyciem przewodów opór powstający na stykach między przewodami w obwodzie przestał być pomijalny.

Jak opisać strukturę drzewa listew oraz opory między przewodami? Allison wymyśliła model matematyczny. Niech $a_i$ oznacza numer $i$-tej listwy, a $f_i$ — listwę, do której podłączona jest jej wtyczka (czyli rodzica $a_i$ w drzewie). Liczby $1$, $2$ i $3$ oznaczają odpowiednio przewód fazowy, neutralny i ochronny. Opory w całym obwodzie można opisać przez $R(a_i,f_i,x,y)$, gdzie $x,y\in\{1,2,3\}$. Jest to opór między przewodem $x$ listwy $a_i$ a przewodem $y$ listwy $f_i$. W tym modelu Allison dopuszcza również połączenie przewodu fazowego z neutralnym i powstanie między nimi oporu. Oto przykład:

Z upływem czasu opory między przewodami mogą się zmieniać. Allison chce teraz znać aktualny opór między przewodem $x$ listwy $a_i$ a przewodem $y$ listwy $a_j$ w obwodzie tworzącym drzewo. Przyjmujemy, że korzeń drzewa listew nie jest podłączony do żadnej innej listwy i ma numer $1$.

Wejście

Pierwszy wiersz pliku wejściowego circuit.in zawiera dodatnią liczbę całkowitą $n$, oznaczającą liczbę listew.

Następne $4(n-1)$ wierszy jest podzielonych na bloki po 4 wiersze.

Pierwszy wiersz $i$-tego bloku zawiera liczbę całkowitą $f_i$, oznaczającą, że rodzicem listwy o numerze $i+1$ jest listwa $f_i$.

Następnie podana jest macierz $g_{xy}$ o wymiarach $3\times3$. Element w wierszu $x$ i kolumnie $y$ jest odwrotnością oporu między przewodem $x$ listwy o numerze $i+1$ a przewodem $y$ listwy $f_i$.

Następnie podana jest liczba całkowita $q$, oznaczająca liczbę operacji.

Każdy z następnych $q$ wierszy zawiera kilka liczb całkowitych.

Pierwszą liczbą jest $k$. Jeśli $k=1$, następują po niej cztery liczby całkowite $a_i,x_i,x_j,g$. Oznacza to zmianę oporu między przewodem $x_i$ listwy $a_i$ a przewodem $x_j$ jej rodzica $f_i$ na odwrotność $g$. Zagwarantowano, że $2\le a_i\le n$.

Jeśli $k=2$, następują po niej cztery liczby całkowite $a_i,x_i,a_j,x_j$. Jest to zapytanie o opór między przewodem $x_i$ listwy $a_i$ a przewodem $x_j$ listwy $a_j$. Zagwarantowano, że $a_i\ne a_j$.

Wyjście

Plik wyjściowy to circuit.out.

Dla każdego zapytania wypisz w osobnym wierszu liczbę rzeczywistą oznaczającą opór między dwoma przewodami.

Wartość oporu uznaje się za poprawną, jeśli

$$\left|\frac{\text{wynik zawodnika}-\text{wynik wzorcowy}}{\text{wynik wzorcowy}}\right|<10^{-3}.$$

Jeśli wszystkie wartości oporu są poprawne, otrzymujesz punkty za dany test.

Przykład

Wejście 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

Wyjście 1

0.083836
0.095256
0.078828
0.146900

Przykład 2

Zobacz pliki circuit/circuit.in i circuit/circuit.ans w katalogu zawodnika.

Ograniczenia

Dla wszystkich danych testowych wejście opisuje drzewo. Każda odwrotność oporu podana na wejściu jest większa od $0$ i nie większa niż $10$.