توجد مصفوفة $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
ملاحظة
تحتوي هذه المسألة على حجم إدخال كبير، يرجى استخدام طريقة إدخال فعالة.