E. Пиглетийн төрсөн өдөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Өнөөдөр Пиглетийн төрсөн өдөр. Түүний найз Вини Пүүх түүнд хамгийн шилдэг бэлэг болох зөгийн балны ваар хийж өгөхийг хүсч байна. Мэдээж Вини Пиклетэд өгөх ваараа дүүрэн эсэхийг нь мэдэх боломжгүй. Үнэндээ Пиглет вааранд буй бүх зөгийн балыг идэх дуртай. Ингээд Вини ваар боломжит хамгийн их зөгийн балтай байх ёстой гэж төлөвлөжээ.

Нэг өдрийн өмнө Вини Пүүх өөрийн зөгийн балны нөөцөө дүүргэсэн. Вини Пүүх гэртээ тус бүр нь хэд хэдэн эсвэл тэг зөгийн балны ваартай байж болох $n$ тавиуртай. Өдрийн турш Вини тавиурууд дээр $q$ удаа ирсэн. Тэр $i$ дахь удаагаа ирэхдээ $u_{i}$ тавиур дээр ирсэн ба $k_{i}$ ваар авч ваар бүрээс зөгийн балыг амтлаад $v_{i}$ тавиур дээр тавьсан. Вини ваарнуудыг зөнгөөрөө сонгосон. Энэ нь $u_{i}$ тавиур дээрээс $k_{i}$ ваартай бүх бүрдлүүдийн дундаас тэнцүү магадлалтайгаар сонгосон гэсэн үг.

Одоо Вини зөгийн балны ваарнуудад хийсэн бүх үйлдлүүдээ санаж байна. Тэр үдэшлэгт өмнөх өдөр амсаагүй ваар авч явахыг хүсч байна. Үүний тулд тэр нэг ч амталгаанд ороогүй ваар байхгүй тавиуруудын тоо болох $m$ тооны математик магадлалыг мэдэхийг хүсч байна. Боломжоо илүү байлгахын тулд Вини Пүүх өөрийн гүйцэтгэсэн үйлдэл бүрийн дараах $m$ утгыг мэдэхийг хүсч байна.

Таны ажил бол түүнд уг утгуудыг олж өгдөг програм бичих юм.

Оролт

Оролтын эхний мөрөнд нэг тоо $n$ ($1 ≤ n ≤ 10^{5}$) байх ба Винигийн гэрт байгаа тавиуруудын тоо байна. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоо $a_{i}$ ($1 ≤ i ≤ n$, $0 ≤ a_{i} ≤ 100$) байх ба $i$-р тавиур дээр байгаа ваарнуудын тоо байна.

Дараагийн мөрөнд бүхэл тоо $q$ ($1 ≤ q ≤ 10^{5}$) байх буюу өмнөх өдөр Винигийн хийсэн үйлдлүүдийн тоо юм. Дараагийн $q$ мөрөнд хийгдсэн үйлдлүүдийг болсон дарааллаар нь хэвлэх ба $i$-р мөрөнд гурван бүхэл тоо $u_{i}$, $v_{i}$ ба $k_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $1 ≤ k_{i} ≤ 5$) байх ба харгалзан Винигийн авсан ваарнууд байсан тавиурын дугаар, Вини амталсан ваарнуудаа тавьсан тавиурын дугаар, Винигийн амталсан ваарнуудын тоо байна.

Ваарны тавиуруудыг 1-с $n$ хүртэл бүхэл тоогоор дугаарлагдсан гэж үз. Мэдээж Вини Пүүх тавиур дээр байгаагаас олон ваар авах гэж оролдохгүй.

Гаралт

Виннигийн үйлдэл бүрийн хувьд $m$ утгын математик таамаглалыг хэвлэнэ үү. Хариуг үйлдлүүдийн болсон дарааллаар хэвлэнэ. Утга бүрийн харьцангуй болон үнэмлэхүй алдаа нь $10^{ - 9}$-с ихгүй байх ёстой.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3
2 2 3
5
1 2 1
2 1 2
1 2 2
3 1 1
3 2 2
Гаралт
0.000000000000
0.333333333333
1.000000000000
1.000000000000
2.000000000000
Сэтгэгдлүүдийг ачааллаж байна...