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

Input

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

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

Note

$3^{27} = 7625597484987$