Тини тооцоололын геометрын хичээл дээр сегмент мод буюу интервал мод гэх ашигтай өгөгдлийн бүтэц үзэж байгаа. Түүнд дараах асуудал тулгарахад энэхүү сэдэвийг ойлгосон байна.

$a_1, a_2, ..., a_n$ жагсаалт болон $q$ хүсэлт өгөгдсөн. Хүсэлт бүр нь дараах хоёр төрөл байна.

• $l,r(1 ≤ l ≤ r ≤ n)$ хоёр тоо өгөгдөнө. $l$-с $r$ завсарын нийлбэрийг олох $a_l, a_l + 1, ..., a_r$.
• $l,r(1 ≤ l ≤ r ≤ n)$ хоёр тоо өгөгдөнө. $l$-с $r$ завсар дахь элемент бүрийг куб зэрэг дэвшүүлэх. Өөрөөр хэлбэл $a_l = a_l^3, a_{l + 1} = a_{l + 1}^3, ..., a_r = a_r^3$.

$1$ төрөлтэй хүсэлт бүрийн хувьд харгалзах хариуг хэвлэ.

Тэр үүнийг тооцоолж чадахгүй учраас таниас тусламж хүссэн байна. Гаралтанд маш том тоо байх тул 95542721(Энэ тоо нь анхны тоо болно) хувааж үлдэгдэлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд $n$ тоо өгөгдөнө. Хоёр дахь мөрөнд хоосон зайгаар тусгаарлагдсан $n$ элементтэй $a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9)$ жагсаалт өгөгдөнө.

Дараагийн мөрөнд хүсэлт болох $q$ тоо өгөгдөнө. Дараагийн $q$ ширхэг мөр бүрт төрлийн тоо $t_i (1 ≤ t_i ≤ 2)$ болон интервалын тоо $ l_i, r_i (1 ≤ l_i ≤ r_i ≤ n)$ өгөгдөнө.

Гаралт

Нэмж хасах $95542721$ ($-95542721 < Хариу < 95542721$) хооронд байна гэдгийг анхаарна уу!