Дээр дээрээсээ давхарлан байрласан $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$).

Гаралт

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