C. Хүмүүст туслах

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

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

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

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

Малек бол баян залуу. Бас тэр өгөөмөр ба энэ нь мөнгөө яагаад ядруухан хүмүүст хувааж өгөхөөр шийдсэн шалтгаан юм. Халамжийн газар $n$ ядруухан амьдралтай хүн мэдэх ба $1$-c $n$ хүртэл дугаарлагдсан. Халамжийн газраас Малекд $q$ санал өгсөн. Санал нь $[l, r]$ сегмент байх ба энэ нь халамжийн газар Малекд энэ сегментэд дугаар нь орших бүх хүнд нэг доллар өгөхийг санал болгож байна гэсэн үг.

Гэсэн хэдий ч халамжийн газар саналуудын хувьд этгээд дүрмүүдтэй. Эдгээр дүрмүүдээс болж саналууд дурын хоёр санал $[a, b]$ ба $[c, d]$-н хувьд дараах нөхцөлүүдийн аль нэг нь биелсэн байхаар өгөгдөнө:

  • Хоёр сегмент ерөөсөө огтлолцохгүй. Өөрөөр $a ≤ b < c ≤ d$ байна эсвэл $c ≤ d < a ≤ b$ байна
  • Хоёр сегментийн нэг нь нөгөөдхөндөө агуулагдана. Өөрөөр $a ≤ c ≤ d ≤ b$ байна эсвэл $c ≤ a ≤ b ≤ d$ байна.

Халамжийн газрын буянт үйл нь Малек мөнгөө өгч дууссаны дараа хүмүүст байгаа мөнгөний хамгийн их утга байна. Халамжийн газар санал бүрийн хувьд Малекийн уг саналыг зөвшөөрөх магадлалыг мэдэж байгаа. Тэд энэ халамжийн газрын дундаж буянт үйлийн утгыг мэдэхийг хүсч байна. Тэд таны тусламжийг хүссэн.

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

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n, q$ ($1 ≤ n ≤ 10^{5}$, $1 ≤ q ≤ 5000$) өгөгдөнө.

Хоёр дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($0 ≤ a_{i} ≤ 10^{9}$) байх ба $i$ дугаартай хүн анх $a_{i}$ доллартай байсан гэсэн үг.

Дараагийн $q$ мөр бүрт зайгаар тусгаарлагдсан гурван бүхэл тоон утга $l_{i}, r_{i}, p_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$, $0 ≤ p ≤ 1$) байх ба энд $l_{i}$ ба $r_{i}$ нь саналыг тодорхойлж байгаа бүхэл тоонууд бол $p_{i}$ нь Малек уг саналыг зөвшөөрөх магадлал ба цэгээс хойш яг гурван оронтой бодит тоо байна.

Саналууд дунд нэг сегмент хэд хэдэн удаа таарч болно.

Гаралт

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

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

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

Оролт
5 2
1 7 2 4 3
1 3 0.500
2 2 0.500
Гаралт
8.000000000
Оролт
5 2
281 280 279 278 282
1 4 1.000
1 4 0.000
Гаралт
282.000000000
Оролт
3 5
1 2 3
1 3 0.500
2 2 0.250
1 2 0.800
1 1 0.120
2 2 0.900
Гаралт
4.465000000
Сэтгэгдлүүдийг ачааллаж байна...