E. Баавгай ба дэд моднуудыг устгах

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

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

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

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

Лимак бол бяцхан хүрэн баавгай юм. Тэрээр Дийрланд хэмээх газар нутаг уруу нэг удаа дайралт хийх боловч одоо тэрээр зөвхөн нэгэн тоглоом дахь моднуудыг устгаж чадах байв. Лимак нэг орой бүхий нэгэн модноос эхлэх юм. Уг нэг орой нь $1$ гэсэн дугаартай бөгөөд уг модны үндэс нь байв.

Зарим үед тоглоом нь нэгэн дэд модыг сонгох бөгөөд Лимак-ыг уг мод уруу дайрахыг зөвшөөрөх ажээ. Ямар нэгэн дэд мод дайралтад өртөх үед уг модны ирмэг болгон нь магадлалтайгаар устах бөгөөд бусад ирмэгүүдтэй ямар нэгэн хамааралгүйгээр устах юм. Дайралтын дараа Лимак уг дэд модны өндрийн хэмжээтэй тэнцүү бүхэл тоон утга бүхий шийтгэл хүртэнэ. Дэд модны өндөр гэдэг нь дэд модны ямар нэгэн орой болон үндэсний хооронд байх зам дээрх хамгийн их ирмэгийн тоог хэлнэ.

Та дараах 2 төрлийн асуултуудад хариулах болно.

  • 1 v гэдэг нь эхний төрлийн асуултыг илэрхийлнэ. Уг асуултын үед шинэ ирмэг гарч ирэх бөгөөд уг ирмэгийн эх орой нь $v$ байх юм. Түүнчлэн шинэ орой нь дараагийн боломжит дугаараар дугаарлагдана. Иймд шинэ орой нь $2, 3, ...$ гэх мэтчилэн дугаарлагдах юм.
  • 2 v гэдэг нь 2-дахь төрлийн асуултыг илэрхийлнэ. Ямар нэгэн мөчид Лимак-ыг $v$ орой дээр үндэстэй нэгэн дэд мод уруу дайрахыг зөвшөөрсөн гэж үзье. Тэгвэл Лимак-ын дайралтын дараа түүний хүртэх ёстой шийтгэлийн хүлээгдэж буй утга нь хэд байх вэ? Энэ нь магадлалын онолын тодорхойлолт бөгөөд Англи хэлэнд $expected$ $value$ хэмээн нэрлэдэг.

2-дахь төрлийн асуултын хувьд Лимак яг үнэндээ уг дэд мод уруу дайралт хийхгүй юм. Иймд уг төрлийн асуултууд нь дараагийн асуултууддаа ямар нэгэн байдлаар нөлөөлөхгүй байна.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $q$ ($1 ≤ q ≤ 500 000$) өгөгдөх ба энэ нь асуултын тоог илэрхийлнэ.

Дараа нь $q$ ширхэг мөр өгөгдөнө. Эдгээрийн $i$-дахь мөр нь 2 ширхэг бүхэл тоо $type_{i}$ болон $v_{i}$ ($1 ≤ type_{i} ≤ 2$) агуулсан байна. Хэрэв $type_{i} = 1$ байвал $v_{i}$ нь шинэ оройн эх оройн дугаарыг илэрхийлэх бөгөөд хэрэв $type_{i} = 2$ байвал та $v_{i}$ дугаартай орой дээр үндэстэй дэд модны хувьд уг асуултын хариултыг хэвлэх хэрэгтэй болох юм.

Түүнчлэн дор хаяж $1$ ширхэг 2-дахь төрлийн асуулт байх бөгөөд өөрөөр хэлбэл бодлогын гаралт нь яасан ч хоосон байхгүй байна.

Мөн $i$-дахь асуулт өгөгдөхөөс өмнө $v_{i}$ дугаартай орой нь аль хэдийн оршин байх юм.

Гаралт

2-дахь төрлийн асуулт болгоны хувьд хэрэв Лимак өгөгдсөн дэд мод уруу дайралт хийсэн бол хүртэх ёстой шийтгэлийн хүлээгдэж буй утгыг илэрхийлэх нэг бодит тоог хэвлэнэ үү. Хэрэв таны хариултын абсолют болон харьцангуй алдаа нь $10^{ - 6}$-аас хэтрэхгүй байвал таны хариултыг зөвөөр тооцох юм.

Тодруулбал: таны хариултыг $a$, шүүх хариултыг $b$ гэж үзье. Хэрэв байвал шалгагч программ таны хариултыг зөвөөр тооцох юм.

Орчуулсан: Баатархүү

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

Оролт
7
1 1
1 1
2 1
1 2
1 3
2 2
2 1
Гаралт
0.7500000000
0.5000000000
1.1875000000
Оролт
8
2 1
1 1
1 2
1 3
1 4
2 1
1 4
2 1
Гаралт
0.0000000000
0.9375000000
0.9687500000

Тэмдэглэл

Доорх зурагт та эхний жишээний зурган дүрслэлийг харж болох юм. Улаан тойргууд нь 2-дахь төрлийн асуултуудыг илэрхийлнэ.

Сэтгэгдлүүдийг ачааллаж байна...