$a_0$, $a_1$, $...$, $a_{n-1}$ гэсэн дугуй дараалал өгөгдөв. Хоёр төрлийн үйлдэл хийж болно:

• $inc(lf, rg, v)$ — энэ үйлдэл нь $[lf, rg]$ хэрчмийн бүх элементийг $v$ тоогоор өсгөнө;
• $rmq(lf, rg)$ — энэ үйлдэл нь $[lf,rg]$ хэрчмийн элементүүдээс хамгийн багыг нь буцаана.

Дугуй хэрчим гэж, хэрвээ $n = 5$ ба $lf = 3$, $rg = 1$ бол энэ нь $3$, $4$, $0$, $1$ дугаартай дарааллыг ойлгоно.

Өгсөн үйлдлүүдийн дарааллын гүйцэтгэх програм бич.

Оролт

Эхний мөр $n$, ($1 ≤ n ≤ 200000$) бүхэл тоог агуулна. Дараагийн мөр анхны дараалал: $a_0$, $a_1$, $...$, $a_{n - 1}$ ($-10^6 ≤ a_i ≤ 10^6$) бүхэл тоонуудыг агуулна. Гуравдахь мөр үйлдлүүдийн тоо болох $m$ ($0 ≤ m ≤ 200000$) бүхэл тоог агуулна. Дараагийн $m$ мөр бүр нэг үйлдэл агуулна. Хэрвээ мөрөнд $lf$, $rg$ ($0 ≤ lf, rg ≤ n - 1$) хоёр бүхэл тоог агуулж байвал энэ нь $rmq$ үйлдэл, $lf$, $rg$, $v$ ($0 ≤ lf, rg ≤ n - 1$; $- 10^6 ≤ v ≤ 10^6$) гурван бүхэл тоог агуулж байвал энэ нь $inc$ үйлдэл гэж ойлгоно.

Гаралт

$rmq$ үйлдэл бүрт түүний үр дүнг бич.