E. Химийн туршилт

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

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

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

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

Нэгэн өдөр Гриша болон Диана нар их сургуулийнхаа химийн лабораторид уулзжээ. Лабораторт $1$-ээс $n$ хүртэл дугаарлагдсан мөнгөн устай шинжилгээний шилнүүд байсан ба тэр хоёр эдгээрээр туршилт хийхээр шийдэв.

Туршилт $q$ алхамтай. Алхам бүрт дараах үйлдлүүдийн нэг нь хийгдэнэ:

  1. Диана $p_{i}$ дугаарын шилийг хоослон дараа нь яг $x_{i}$ литр мөнгөн ус хийнэ.
  2. Шилнүүдэд $v_{i}$ литр ус нэмэх бүх боломжуудыг авч үзье. Боломж бүрт ус агуулж буй хамгийн их шингэнтэй (ус болон мөнгөн устай) шилэн доторх шингэний хэмжээг (ус болон мөнгөн усны нийт хэмжээг) олъё. Эцэст нь тэдгээр утгуудаас хамгийн бага утгыг тэмдэглэнэ. Энэ утга л тэдний олохыг хүссэн зүйл. Тэд мөнгөн усыг асгахгүй. Тэд мөн шилэн доторх зүйлсэд өөрчлөлт оруулахгүйгээр зөвхөн тоог л тэмдэглэж авах ёстой.

Харамсалтай нь тооцоолол хэт хүнд байсан тул оюутнууд чамайг туслахыг хүсчээ. Тэдэнд туршилтийг хийхэд нь туслана уу.

Оролт

Эхний мөрөнд туршилтын шилний тоо болон туршилтын алхмуудын тоог илэрхийлэх $n$ ба $q$ ($1 ≤ n, q ≤ 10^{5}$) гэсэн бүхэл тоонууд байна. Дараагийн мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан $h_{1}, h_{2}, ..., h_{n}$ ($0 ≤ h_{i} ≤ 10^{9}$) тоонууд байх ба $h_{i}$ нь $і$ дугаарын шилэнд байгаа мөнгөн усны хэмжээ.

Дараагийн $q$ мөрөнд үйлдлүүд дараахь форматтайгаар өгөгдөнө:

  • "$1$ $p_{i}$ $x_{i}$" хэлбэртэй мөр нь нэгдүгээр төрлийн үйлдлийг илэрхийлнэ ($1 ≤ p_{i} ≤ n; 0 ≤ x_{i} ≤ 10^{9}$).
  • "$2$ $v_{i}$" хэлбэрийн мөр нь хоёрдугаар төрлийн үйлдийг илэрхийлнэ ($1 ≤ v_{i} ≤ 10^{15}$).

Өгөгдөлд дор хаяж нэг удаа хоёрдугаар төрлийн үйлдэл өгөгдөнө. Туршилтыг илэрхийлж буй тоонууд бүгд бүхэл тоо байх болно.

Гаралт

Хоёрдугаар төрлийн үйлдэл өгөгдөх бүрт тооцоолж гаргасан тоог хэвлэ. Хариу абсолют утгаараа $10^{ - 4}$-аас бага алдаатай бол зөв хариунд тооцогдоно.

Орчуулсан: Бат-Од

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

Оролт
3 3
1 2 0
2 2
1 2 1
2 3
Гаралт
1.50000
1.66667
Оролт
4 5
1 3 0 1
2 3
2 1
1 3 2
2 3
2 4
Гаралт
1.66667
1.00000
2.33333
2.66667
Сэтгэгдлүүдийг ачааллаж байна...