D. Усны савнууд

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

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

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

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

Дээр дээрээсээ давхарлан байрласан $n$ усны саваас тогтох систем зурагт үзүүлснээр оршино. Усны савууд дээрээс доошоо $1$-с $n$ хүртэл дугаарлагдсан бөгөөд $i$-р савны эзэлхүүн $a_i$ гэж үзье.

Анх бүх сав хоосон байсан. $i$-р сав халих үед халисан ус нь ($i+1$) саванд ордог. $n$-р савнаас хальсан ус шалан дээр асгарна.

Таны даалгавар үйлдлийн дарааллыг гүйцэтгэх процессийг загварчлах юм. Энд дараах $2$ төрлийн үйлдэл байна:

  • $p_i$-р саванд $x_i$ литр ус нэмэх
  • $k_i$-р саванд байгаа усны хэмжээг хэвлэх

Та $2$ төрлийн хүсэлтийг биелүүлэх үед бүх ус урсаж, хальж дууссан байна гэж үзээрэй.

Оролт

Эхний мөрөнд савны тоо $n$ ($1 ≤ n ≤ 2·10^5$) байна. Дараагийн мөрөнд савны эзэлхүүнүүдийг илэрхийлэх $a_1, a_2, ... , a_n$ ($1 ≤ a_i ≤ 10^9$) дараалал өгөгдөнө. Савны эзэлхүүнүүд дээрээс доош ихсэх албагүйг анхаараарай (хоёрдугаар жишээ тестийг хар). Гуравдугаар мөрөнд хүсэлтийн тоо $m$ ($1 ≤ m ≤ 2·10^5$) байна. Дараагийн $m$ мөрөнд хүсэлтийн мэдээлэл байрлана. Эхний төрлийн хүсэлт "$1 p_i x_i$" хэлбэртэй, хоёрдугаар төрлийн хүсэлт "$2 k_i$" хэлбэртэй ($1 ≤ p_i ≤ n$, $1 ≤ x_i ≤ 10^9$, $1 ≤ k_i ≤ n$).

Гаралт

Хоёрдугаар төрлийн хүсэлт бүрт харгалзах саванд байгаа усны хэмжээг хэвлэ.

Орчуулсан: zoloogg

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

Оролт
2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2
Гаралт
4
5
8
Оролт
3
5 10 8
6
1 1 12
2 2
1 1 6
1 3 2
2 2
2 3
Гаралт
7
10
5
Сэтгэгдлүүдийг ачааллаж байна...