G. Сугалаа

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

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

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

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

Жони $n$ сугалаатай багт наадам дээр байна. $i$-р сугалаа $p_{i}$ утгатай хонжвортой. Оролцогч бүр тасалбаруудаа сонгосон дурын сугалаандаа тавьж болно (тэд нэг сугалаанд олон тасалбартай байж болно). Багт наадмын төгсгөлд сугалаа бүрээс нэг тасалбар сонгох ба уг тасалбарын эзэн холбогдох хонжворыг хожно. Нэг хүн ялгаатай сугалаануудаас олон хонжвор хожиж болно.

Гэсэн ч мужийн дүрмэнд нэг сугалаанд байгаа тасалбаруудын талаас ихийг нь нэг оролцогч эзэмшихээс сэргийлдэг, өөрөөр бусад оролцогчдоос цуглуулсан тасалбаруудаас их тасалбар тавьж болохгүй гэсэн үг. Үүнтэй тэмцэхийн тулд зохион байгуулагчид сугалаа бүр дээр хэзээ ч устгахгүй нэг тасалбар тавьж эхэлсэн (мөн хонжвор хожиж болно).

Жони $t$ ширхэг тасалбар авсан ба тэднийг хаана байрлуулахаа мэдэхгүй байна. Одоогоор $i$-р сугалаанд нийтдээ $l_{i}$ тасалбар байгаа. Тэр бусад оролцогчдыг тасалбараа байрлуулаад, шийдвэрээ өөрчилж байгааг харж байгаа ба хугацааны агшин бүрт тэр хэр ихийг цуглуулж чадахаа мэдэхийг хүсч байна. Хэрвээ тэр тасалбаруудаа хамгийн тохиромжтойгоор байрлуулсан бол мөч бүрт түүний хожиж чадах хонжворын боломжит хамгийн их дундаж утгыг ол. Жони шинэчлэл бүрт өөрийн бүх тасалбаруудаа дахин тарааж болох боловч $t$-с их тасалбар байрлуулахгүй эсвэл нэг сугалаанд бусад оролцогчдоос цугласан тасалбараас олон тасалбар тавихгүй.

Оролт

Эхний мөрөнд гурван бүхэл тоон утга $n$, $t$, ба $q$ ($1 ≤ n, t, q ≤ 200 000$) байх буюу харгалзан сугалааны тоо, Жонид байгаа тасалбарын тоо, болон нийт шинэчлэлүүдийн тоо байна.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоон утга $p_{i}$ ($1 ≤ p_{i} ≤ 1000$) байх буюу $i$-р хонжворын утга байна.

Гурав дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоон утга $l_{i}$ ($1 ≤ l_{i} ≤ 1000$) байх буюу $i$-р сугалаанд анх байсан тасалбарын тоо.

Дараагийн $q$ мөрөнд шинэчлэлүүдийн тайлбар байна. Тайлбар бүр хоёр бүхэл тоон утга $t_{k}$, $r_{k}$ ($1 ≤ t_{k} ≤ 2$, $1 ≤ r_{k} ≤ n$) агуулах ба шинэчлэлийн төрөл болон сугалааны дугаар юм. $1$ төрлийн шинэчлэл нь $r_{k}$ сугалаанд өөр оролцогч тасалбар нэмж байгааг илэрхийлнэ. $2$ төрлийн шинэчлэл нь $r_{k}$ сугалаанаас өөр оролцогч тасалбараа хасч байгааг илэрхийлнэ.

Шинэчлэл бүрийн дараа сугалаа бүрт ядаж $1$ тасалбар (Жонигийнхийг оруулахгүйгээр) байна.

Гаралт

Тус бүртээ $k$-р шинэчлэлийн дараах Жонигийн хонжворын боломжит хамгийн их дундаж утгыг илэрхийлэх бодит тоог агуулсан $q$ мөр хэвлэнэ. Хэрвээ таны хариултын үнэмлэхүй болон харьцангуй алдаа нь $10^{ - 6}$-с хэтрэхгүй бол зөвд тооцогдоно.

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

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

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

Оролт
2 1 3
4 5
1 2
1 1
1 2
2 1
Гаралт
1.666666667
1.333333333
2.000000000
Оролт
3 20 5
6 8 10
6 6 6
1 1
1 2
1 3
2 3
2 3
Гаралт
12.000000000
12.000000000
11.769230769
12.000000000
12.000000000

Тэмдэглэл

Эхний тохиолдолд Жонид тараах ганц тасалбар байна. Шагналууд нь $4$ болон $5$ өртөгтэй ба сугалаанууд анх харгалзан $1$ болон $2$ тасалбартай байсан. Эхний шинэчлэлийн дараа сугалаа бүр $2$ тасалбартай болох ба Жони хоёр дахь сугалаанд тасалбараа байрлуулснаар утга бүхий хонжвор хожно. Хоёр дахь шинэчлэлд хоёр дахь сугалаанд тасалбар нэмэх ба Жони эхний сугалаанаас -г хожиж чадна. Сүүлийн шинэчлэлийн дараа Жони тасалбараа эхний сугалаанд хэвээр үлдээх ба -г хожно.

Хоёр дахь тохиолдолд Жони үрж болохоосоо олон тасалбартай байна. Эхний шинэчлэлийн дараа сугалаа бүрт харгалзан $7$, $6$, ба $6$ тасалбар байх ба Жони зөвхөн $19$ тасалбар л тавьж болох ба хонжвор бүрийг магадлалтайгаар хожно. Мөн сүүлийн хоёр шинэчлэлийн дараа Жони гурав дахь сугалаанд -с цөөхөн тасалбартай үлдэхийн тулд сүүлийн сугалаанаас тасалбар хасах ёстой.

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