← 返回题目列表

Codeforces · 906/D

D. 电力塔

中文机器翻译题面 查看原题

羽蛇神教的牧师想要建造一座塔来代表他们神的力量。塔通常由带电岩石制成。它是在稀有魔法的帮助下建造的,通过悬浮当前的塔顶并在其底部添加岩石来建造。如果由 k - 1 块岩石建造的顶部拥有能量 p,并且我们想要添加带有能量 wk 的岩石,那么新塔的能量值为 {wk}p。

岩石从最后一个添加到第一个。即对于序列 w1, ..., wm 功率值将是

$${ w _ { 1 } \left( { w _ { 2 } ^ { ( w _ { 3 } ^ { \cdots w _ { m } } ) } } \right) }$$

塔建成后,威力可能会非常大。但牧师们仍然想获得一些有关它的信息,即他们想知道一个称为累积功率的数字,它是对 m 取模的功率的真实值。祭司有n块岩石,编号从1到n。他们要求你计算,如果他们用编号为 l、l + 1、...、r 的岩石建造这座塔,那么该塔将拥有多少累积能量。

输入

输入的第一行包含两个整数 n (1 ≤ n ≤ 105) 和 m (1 ≤ m ≤ 109)。

输入的第二行包含n个整数wk (1 ≤ wk ≤ 109),这是牧师拥有的岩石力量。

输入的第三行包含单个整数 q (1 ≤ q ≤ 105),这是牧师向您询问的数量。

接下来 q 行的第 k 行包含两个整数 lk 和 rk (1 ≤ lk ≤ rk ≤ n)。

输出

输出 q 个整数。如果塔是用岩石 lk, lk + 1, ..., rk 建造的,那么其中的第 k 项必须是塔所具有的累积功率。

示例

输入 #1

6 1000000000
1 2 2 3 3 3
8
1 1
1 6
2 2
2 3
2 4
4 4
4 5
4 6

输出 #1

1
1
2
4
256
3
27
597484987

注意

327 = 7625597484987