C. Мөөгөн гномууд - 2

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

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

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

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

Нэгэн өдөр Наталиа ойд алхаж явахдаа бяцхан мөөгөн гномууд-той таарчээ. Тэрхүү гном түүнд энэхүү түүхийг ярьж өгөв.

Бүгд мөөгөн гномуудын хүч нь уугуул моддын хажууд ургах шидэх мөөгнөөс хамаардаг гэдгийг мэддэг. Тэнд $n$ мод болон $m$ шидэт мөөгнүүд байгаа : $i$-р мод нь шулуун дээр $a_{i}$ координатад $h_{i}$ өндөртэй ургадаг, $j$-р мөөг шулуун дээр $b_{j}$ координатад $z_{j}$ хэмжээний шидийн хүчтэй ургаж байдаг.

Гэхдээ нэгэн өдөр мөөгөн гномуудын дайсан болох Мөөгөн-Ангууч ойд нь шуурга дэгдээжээ. Үүнээс болж зарим моднууд унаж мөөгнүүдийг бяцлах болжээ. Мөөгөн гномуудын толгойлогч бүх модны хувьд зүүн тийш унах, баруун тийш унах, эсвэл тогтож үлдэх магадлалуудыг бодож олжээ. Хэрэв $x$ координатад байгаа $h$ өндөртэй мод зүүн тийш унавал $[x - h, x)$ завсарт байгаа мөөгнүүд бяцрана. Харин баруун тийш унавал $(x, x + h]$ завсарт байгаа мөөгнүүд бяцарна. Ямар нэгэн модонд дээрээс нь унаагүй мөөг бяцрахгүй үлдэнэ.

Мод болгон бусдаас хамааралгүйгээр унана. (Өөрөөр хэлбэл, моднууд харилцан бие даасан шинж чанартай байдаг. Моднуудын унах чиглэл бусад моднуудаас хамаарахгүй.) Мөөгөн гномуудын толгойлогч шуурганы дараах үлдэх бүх мөөгнүүдийн шидэт хүчний нийлбэрийн хүсэмжит утгыг тооцоолж олсноор мөөгөн гномуудыг аймшигт аюулаас аварсан юм.

Наталиа, сайн Олимпиадын програмистын хувьд энэ түүх түүний сонирхлыг татжээ. Тэр энэхүү шуурганы дараах үлдэх бүх мөөгнүүдийн шидэт хүчний нийлбэрийн хүсэмжит утгыг хурдан тооцоолох аргыг олохоор болжээ.

Оролт

Эхний мөрөнд $n$ болон $m$ бүхэл тоо ($1 ≤ n ≤ 10^{5}$, $1 ≤ m ≤ 10^{4}$) - харгалзан мод болон мөөгний тоо.

Дараагийн $n$ мөр дөрвөн бүхэл тоо агуулна - $a_{i}$, $h_{i}$, $l_{i}$, $r_{i}$ ($|a_{i}| ≤ 10^{9}$, $1 ≤ h_{i} ≤ 10^{9}$, $0 ≤ l_{i}, r_{i}, l_{i} + r_{i} ≤ 100$), харгалзан $i$-р модны координат, өндөр, зүүн болон баруун тийш унах магадлал. (Үлдсэн магадлал нь мод унахгүй байх магадлал юм.)

Дараагийн $m$ мөр хоёр тоо агуулана. $b_{j}$, $z_{j}$ ($|b_{j}| ≤ 10^{9}$, $1 ≤ z_{j} ≤ 10^{3}$), $j$-р шидэт мөөгний координат болон шидэт хүчний утга. Хэчнээн ч тооны мод болон мөөг нэг цэг дээр ургаж болно.

Гаралт

Шуурганы дараах үлдэх бүх мөөгнүүдийн шидэт хүчний нийлбэрийн хүсэмжит утга болох бодит тоог таслалаас хойш 4 оронтой хэвлэ.

Орчуулсан: Б.Алтангэрэл

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

Оролт
1 1
2 2 50 50
1 1
Гаралт
0.5000000000
Оролт
2 1
2 2 50 50
4 2 50 50
3 1
Гаралт
0.2500000000

Тэмдэглэл

$l ≤ x < r$ нөхцлийг хангах $x$ нь $[l, r)$ завсарт агуулагдана. Үүнтэй адилаар $l < x ≤ r$ нөхцлийг хангах $x$ нь $(l, r]$ завсарт агуулагдана.

Эхний жишээнд мөөг мод хаашаа унахаас шалтгаалан 50% магадлалтайгаар тэсэж үлдэнэ.

Хоёрдахь тестэнд хоёр мод хоёулаа унахгүй бол тэсэж үлдэнэ. Энэ нь 50% $ × $ 50% = 25% магадлалтай.

№12 жишээ тест $10^{5}$ ширхэг мод, ганцхан мөөгийг агуулна.

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