ישנו מערך $a$ באורך $n$, שבו המספר ה-$i$ הוא $a_i$. בנוסף, לכל מספר יש ניקוד, והניקוד של המספר ה-$i$ הוא $c_i$. Alice ו-Bob משחקים בתורות, כאשר Alice מתחילה ראשונה.
בסיבוב הנוכחי, השחקן מעתיק תחילה את המערך $a$ למערך $b$ ומריץ תוכנית ערבוב אקראי כדי לערבב באקראי את המערך $b$. באופן ספציפי, תוכנית הערבוב האקראי תבחר אחת מהתמורות של $b$ בהסתברות שווה ותחליף בה את המערך המקורי $b$. נניח שהאורך הנוכחי של המערך $a$ הוא $m$, אזי השחקן יכול לבחור מספר שלם $k$ כך ש-$0 \le k \le m$ וכן $a[1 \dots k] = b[1 \dots k]$, ואז למחוק את $a[1 \dots k]$ (כלומר, הרישא באורך $k$ של $a$) ולקבל את הניקוד של המספרים שנמחקו. המשחק מסתיים כאשר המערך $a$ מתרוקן.
שימו לב שהמערך $a$ ומערך הניקוד שלו $c$ לא יעורבבו לאורך כל התהליך, אלא רק הרישות שלהם יוסרו.
גם Alice וגם Bob רוצים למקסם את הניקוד שלהם. Alice רוצה לדעת מהי תוחלת הניקוד שלה כאשר שני השחקנים נוקטים באסטרטגיות אופטימליות.
Alice גם ביצעה $q$ קבוצות של שינויים (שינוי המערך והניקוד), והיא רוצה שתמצאו את התשובה עבור המערך ההתחלתי, וכן את התשובות לאחר כל קבוצת שינויים.
קלט
השורה הראשונה מכילה מספר שלם $n$ ($1 \le n \le 10^6$), המייצג את אורך המערך ההתחלתי $a$.
השורה השנייה מכילה $n$ מספרים שלמים $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), המייצגים את המערך ההתחלתי $a$.
השורה השלישית מכילה $n$ מספרים שלמים $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), המייצגים את הניקוד של כל מספר במערך.
השורה הבאה מכילה מספר שלם $q$ ($0 \le q \le 10$), המייצג את מספר קבוצות השינויים.
להלן מתוארות $q$ קבוצות של שינויים:
עבור כל קבוצת שינויים, השורה הראשונה מכילה את $k_i$ ($1 \le k_i \le 10^5$), המציין את מספר השינויים בקבוצה זו.
$k_i$ השורות הבאות מכילות כל אחת שלושה מספרים שלמים $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), המציינים ש-$a_{p_j}$ משתנה ל-$x_j$ ו-$c_{p_j}$ משתנה ל-$y_j$.
מובטח כי $p_1 < p_2 < \dots < p_{k_i}$.
פלט
הדפיסו בסך הכל $q + 1$ שורות, כאשר כל שורה מכילה מספר נקודה צפה המייצג את התשובה.
השורה הראשונה היא התשובה עבור המערך ההתחלתי, ואחריה $q$ שורות עבור התשובות לאחר כל קבוצת שינויים.
תשובה תיחשב נכונה אם השגיאה היחסית או המוחלטת בהשוואה לתשובה התקנית אינה עולה על $10^{-9}$.
דוגמאות
קלט 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
פלט 1
1.333333333333 3.000000000000 4.000000000000
קלט 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
פלט 2
9.013888888889
הערה
לבעיה זו יש קלט גדול, אנא השתמשו בשיטת קלט יעילה.