มีอาเรย์ $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
หมายเหตุ
โจทย์ข้อนี้มีขนาดข้อมูลนำเข้าขนาดใหญ่ โปรดใช้วิธีการอ่านข้อมูลที่มีประสิทธิภาพ