CF906D.Power Tower

Priests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the current top of tower and adding rocks at its bottom. If top, which is built from k - 1 rocks, possesses power p and we want to add the rock charged with power w__k then value of power of a new tower will be {w__k}p.

Rocks are added from the last to the first. That is for sequence _w_1, ..., w__m value of power will be

After tower is built, its power may be extremely large. But still priests want to get some information about it, namely they want to know a number called cumulative power which is the true value of power taken modulo m. Priests have n rocks numbered from 1 to n. They ask you to calculate which value of cumulative power will the tower possess if they will build it from rocks numbered l, l + 1, ..., r.

魁扎尔科亚特尔教派的祭司们希望建造一座高塔，以彰显他们神明的力量。这座高塔通常由蕴含能量的岩石堆砌而成。借助一种稀有的魔法，人们通过使当前塔顶悬浮，并在塔底添加新的岩石来建造高塔。若当前塔顶由 $k-1$ 块岩石构成，其能量值为 $p$，而新加入的第 $k$ 块岩石所蕴含的能量为 $w_k$，则新高塔的能量值为 $w_k^p$。

岩石按从后往前的顺序添加。即，对于序列 $w_1, \dots, w_m$，最终高塔的能量值为：

高塔建成后，其能量值可能极其巨大。但祭司们仍希望获取一些相关信息，具体而言，他们希望知道一个称为“累积能量”的数值，即该能量值对 $m$ 取模后的结果。祭司们拥有编号为 $1$ 到 $n$ 的 $n$ 块岩石。他们请你计算：若仅使用编号为 $l, l+1, \dots, r$ 的岩石来建造高塔，则该高塔的累积能量值是多少？

First line of input contains two integers n (1 ≤ n ≤ 105) and m (1 ≤ m ≤ 109).

Second line of input contains n integers w__k (1 ≤ w__k ≤ 109) which is the power of rocks that priests have.

Third line of input contains single integer q (1 ≤ q ≤ 105) which is amount of queries from priests to you.

k__th of next q lines contains two integers l__k and r__k (1 ≤ l__k ≤ r__k ≤ n).

输入的第一行包含两个整数 $n$（$1 ≤ n ≤ 10^5$）和 $m$（$1 ≤ m ≤ 10^9$）。

输入的第二行包含 $n$ 个整数 $w_k$（$1 ≤ w_k ≤ 10^9$），表示祭司所拥有的岩石的力量值。

输入的第三行包含一个整数 $q$（$1 ≤ q ≤ 10^5$），表示祭司向你提出的查询次数。

接下来的 $q$ 行中，第 $k$ 行包含两个整数 $l_k$ 和 $r_k$（$1 ≤ l_k ≤ r_k ≤ n$）。

Output q integers. k-th of them must be the amount of cumulative power the tower will have if is built from rocks l__k, l__k + 1, ..., r__k.

输出 q 个整数。其中第 k 个整数表示：若用编号为 l__k, l__k + 1, ..., r__k 的石头建造塔，则该塔的总能量值。

327 = 7625597484987

$327 = 7625597484987$