Terdapat sebuah larik $a$ dengan panjang $n$, di mana bilangan ke-$i$ adalah $a_i$. Selain itu, setiap bilangan memiliki skor, dan skor dari bilangan ke-$i$ adalah $c_i$. Alice dan Bob bermain secara bergiliran, dengan Alice melangkah lebih dulu.
Pada ronde saat ini, pemain pertama-tama menyalin larik $a$ ke larik $b$ dan menjalankan program pengacakan acak untuk mengacak larik $b$ secara acak. Secara spesifik, program pengacakan acak akan memilih salah satu permutasi dari $b$ dengan peluang yang sama dan menggantikan larik $b$ semula dengannya. Misalkan panjang larik $a$ saat ini adalah $m$, maka pemain dapat memilih sebuah bilangan bulat $k$ sedemikian sehingga $0 \le k \le m$ dan $a[1 \dots k] = b[1 \dots k]$, lalu menghapus $a[1 \dots k]$ (yaitu prefiks sepanjang $k$ dari $a$) dan memperoleh skor dari bilangan-bilangan yang dihapus. Permainan berakhir ketika larik $a$ menjadi kosong.
Perhatikan bahwa larik $a$ dan larik skornya $c$ tidak akan diacak sepanjang seluruh proses, melainkan hanya prefiksnya saja yang dihapus.
Baik Alice maupun Bob ingin memaksimalkan skor mereka. Alice ingin mengetahui berapa nilai harapan skornya ketika kedua pemain menerapkan strategi optimal.
Alice juga melakukan $q$ kelompok modifikasi (memodifikasi larik dan skor), dan ia ingin Anda mencari jawaban untuk larik awal, serta jawaban setelah setiap kelompok modifikasi.
Masukan
Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^6$), yang menyatakan panjang larik awal $a$.
Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), yang menyatakan larik awal $a$.
Baris ketiga berisi $n$ bilangan bulat $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), yang menyatakan skor dari setiap bilangan di dalam larik.
Baris berikutnya berisi sebuah bilangan bulat $q$ ($0 \le q \le 10$), yang menyatakan banyaknya kelompok modifikasi.
Bagian berikut mendeskripsikan $q$ kelompok modifikasi:
Untuk setiap kelompok modifikasi, baris pertama berisi $k_i$ ($1 \le k_i \le 10^5$), yang menyatakan banyaknya modifikasi dalam kelompok ini.
$k_i$ baris berikutnya masing-masing berisi tiga bilangan bulat $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), yang menyatakan bahwa $a_{p_j}$ diubah menjadi $x_j$ dan $c_{p_j}$ diubah menjadi $y_j$.
Dijamin bahwa $p_1 < p_2 < \dots < p_{k_i}$.
Keluaran
Keluarkan total $q + 1$ baris, masing-masing baris berisi sebuah bilangan titik-mengambang yang menyatakan jawabannya.
Baris pertama adalah jawaban untuk larik awal, diikuti oleh $q$ baris untuk jawaban setelah setiap kelompok modifikasi.
Jawaban dianggap benar jika galat relatif atau absolut dibandingkan dengan jawaban standar tidak melebihi $10^{-9}$.
Contoh
Masukan 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Keluaran 1
1.333333333333 3.000000000000 4.000000000000
Masukan 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Keluaran 2
9.013888888889
Catatan
Persoalan ini memiliki ukuran masukan yang besar, harap gunakan metode pembacaan masukan yang efisien.