羽蛇神教的牧师想要建造一座塔来代表他们神的力量。塔通常由带电岩石制成。它是在稀有魔法的帮助下建造的,通过悬浮当前的塔顶并在其底部添加岩石来建造。如果由 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