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*<sub class="lower-index">*k*</sub> then value of power of a new tower will be {*w*<sub class="lower-index">*k*</sub>}<sup class="upper-index">*p*</sup>. 

Rocks are added from the last to the first. That is for sequence *w*<sub class="lower-index">1</sub>, ..., *w*<sub class="lower-index">*m*</sub> 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<sup class="upper-index">5</sup>) and *m* (1 ≤ *m* ≤ 10<sup class="upper-index">9</sup>).

Second line of input contains *n* integers *w*<sub class="lower-index">*k*</sub> (1 ≤ *w*<sub class="lower-index">*k*</sub> ≤ 10<sup class="upper-index">9</sup>) which is the power of rocks that priests have.

Third line of input contains single integer *q* (1 ≤ *q* ≤ 10<sup class="upper-index">5</sup>) which is amount of queries from priests to you.

*k*<sup class="upper-index">*th*</sup> of next *q* lines contains two integers *l*<sub class="lower-index">*k*</sub> and *r*<sub class="lower-index">*k*</sub> (1 ≤ *l*<sub class="lower-index">*k*</sub> ≤ *r*<sub class="lower-index">*k*</sub> ≤ *n*).
3<sup class="upper-index">27</sup> = 7625597484987
tmp=input()
tmp=tmp.split()
n=eval(tmp[0])
mod=eval(tmp[1])
arr=[]
arr=input()
arr=arr.split()

num=eval(input())
def powertower(a,b):
    if arr[a]=='1' or a==b:
        return int (arr[a])

    elif a+1!=b:
        return pow(int (arr[a]),powertower(a+1,b))
    
    else:
        return pow(int (arr[a]),int (arr[b]))
def main():

    for i in range(int(num)):
        k=input() 
        k=k.split()
        x=int(k[0])
        y=int(k[1])
        ans=int(powertower(x-1,y-1))
        print(ans%mod)

main()

