Програмчлалын олимпиадын бодлогын архив

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

Батад a₁, a₂, . . . , 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³, a_{l + 1} = a_{l + 1}³, . . . , a_r = a_r³.

Бат эдгээр хүсэлтүүдэд хариу өгч чадахгүй учраас таниас тусламж хүссэн байна.

1 дугаартай хүсэлт бүрийн хувьд харгалзах хариуг хэвлэ.  Гаралтанд маш том тоо байх учраас 95542721 хуваасны үлдэгдэлийг хэвлэнэ үү.

Input

Эхний мөрөнд n тоо өгөгдөнө. Хоёр дахь мөрөнд хоосон зайгаар тусгаарлагдсан n(1 ≤ n ≤ 105) элементтэй a₁, a₂, . . . , a_n(0 ≤ a_i ≤ 10⁹)жагсаалт өгөгдөнө.
Дараагийн мөрөнд хүсэлт болох q тоо өгөгдөнө. Дараагийн q (1 ≤ q ≤ 105) ширхэг мөр бүрт төрлийн тоо t_i(1 ≤ t_i ≤ 2) болон интервалын тоо l_i,r_i (1 <=l_i, r_i <=n) өгөгдөнө.

Output

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

Example

Input:

10
10 10 0 4 0 6 5 4 2 8
10
1 2 3
2 1 5
1 7 8
2 1 9
2 3 8
2 3 6
2 1 10
1 6 8
2 3 7
1 1 4
Output:

10

9

88844453

11661634