ל־Allison יש מכשירים אלקטרוניים רבים מאוד, למשל iMac, iPod, iPhone ו־iPad. לכן היא מתכננת לקנות מפצלי שקעים כדי לטעון אותם. לאחר מחקר נרחב באינטרנט, Allison מצאה מפצל שקעים יפה ומעוצב של המותג 天翼, כפי שמוצג בתמונה השמאלית למטה. כבר במבט הראשון היא הוקסמה מעיצובו, ולכן קנתה בבת אחת $n$ מפצלים מהדגם הזה.

אלא שאז התעוררה בעיה: בביתה של Allison יש רק שקע אחד. עליה לחבר את המפצלים זה לזה כדי להעביר את החשמל משכבה לשכבה, כפי שמוצג בתמונה הימנית למעלה.

חיבור המפצלים יוצר מבנה של עץ: התקע של כל מפצל מחובר לשקע במפצל אחר, למעט השורש. אסור שהחיבורים ייצרו מעגל.

בכל מפצל יש שלושה מוליכים: פאזה, אפס והארקה. ככל שמספר המפצלים גדל והמוליכים נשחקים, ההתנגדות הנוצרת במגע בין המוליכים במעגל כבר אינה זניחה.

כיצד אפשר לתאר את מבנה העץ של המפצלים ואת ההתנגדויות בין המוליכים? Allison הגתה מודל מתמטי: $a_i$ הוא מספרו של המפצל ה־$i$, ו־$f_i$ הוא המפצל שאליו מחובר התקע שלו, כלומר האב של $a_i$ בעץ. המספר 1 מציין את מוליך הפאזה, 2 את מוליך האפס ו־3 את מוליך ההארקה. ההתנגדויות במעגל מתוארות באמצעות $R(a_i,f_i,x,y)$, כאשר $x,y\in\{1,2,3\}$. זהו ערך ההתנגדות בין המוליך $x$ של $a_i$ למוליך $y$ של $f_i$. במודל זה Allison מניחה שגם מוליכי הפאזה והאפס עשויים להיות מחוברים זה לזה וליצור התנגדות. להלן דוגמה:

עם הזמן ההתנגדויות בין המוליכים עשויות להשתנות. כעת Allison רוצה לדעת מהי ההתנגדות ברגע הנוכחי בין המוליך $x$ במפצל $a_i$ למוליך $y$ במפצל $a_j$, במעגל המפצלים בעל מבנה העץ. שורש העץ אינו מחובר למפצל אחר, ומספרו 1.

קלט

השורה הראשונה בקובץ הקלט circuit.in מכילה מספר שלם חיובי $n$, מספר המפצלים.

אחריה באות $4(n-1)$ שורות, המחולקות לבלוקים של 4 שורות.

השורה הראשונה בבלוק ה־$i$ מכילה מספר שלם $f_i$, המציין שהאב של המפצל שמספרו $i+1$ הוא המפצל $f_i$.

אחריה באה מטריצה $g_{xy}$ בגודל $3\times3$. האיבר בשורה $x$ ובעמודה $y$ הוא הערך ההופכי של ההתנגדות בין המוליך $x$ של המפצל שמספרו $i+1$ למוליך $y$ של $f_i$.

לאחר מכן מופיע מספר שלם $q$, מספר הפעולות.

כל אחת מ־$q$ השורות הבאות מכילה כמה מספרים שלמים.

המספר הראשון הוא $k$. אם $k=1$, אחריו באים ארבעה מספרים שלמים $a_i,x_i,x_j,g$. פעולה זו משנה את ההתנגדות בין המוליך $x_i$ של המפצל $a_i$ למוליך $x_j$ של אביו $f_i$ לערך ההופכי של $g$. מובטח כי $2\le a_i\le n$.

אם $k=2$, אחריו באים ארבעה מספרים שלמים $a_i,x_i,a_j,x_j$. זוהי שאילתה על ההתנגדות בין המוליך $x_i$ של המפצל $a_i$ למוליך $x_j$ של המפצל $a_j$. מובטח כי $a_i\ne a_j$.

פלט

קובץ הפלט הוא circuit.out.

עבור כל שאילתה, יש להדפיס בשורה נפרדת מספר ממשי המייצג את ההתנגדות בין שני המוליכים.

ערך התנגדות ייחשב נכון אם

$$ \left|\frac{\text{פלט המתחרה}-\text{פלט הייחוס}}{\text{פלט הייחוס}}\right|<10^{-3}. $$

אם כל ערכי ההתנגדות נכונים, מתקבל הניקוד עבור אותו מקרה בדיקה.

דוגמאות

קלט 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

פלט 1

0.083836
0.095256
0.078828
0.146900

קלט ופלט 2

ראו את הקבצים circuit/circuit.in ו־circuit/circuit.ans בתיקיית המתחרה.

מגבלות

בכל נתוני הבדיקה מובטח שהקלט הוא עץ. הערך ההופכי של כל התנגדות בקלט גדול מ־$0$ ואינו עולה על $10$.