A11555. 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$ .

First line of input contains two integers $n$ ( $1<=n<=10^{5}$ ) and $m$ ( $1<=m<=10^{9}$ ).

Second line of input contains $n$ integers $w_{k}$ ( $1<=w_{k}<=10^{9}$ ) which is the power of rocks that priests have.

Third line of input contains single integer $q$ ( $1<=q<=10^{5}$ ) 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$ ).

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}$ .

$3^{27}=7625597484987$