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
class Tower:

    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.w = []
        self.q = 0

    def add_w(self, w):
        self.w.append(w)

    def set_q(self, q):
        self.q = q

    def ask(self, left, right):
        num = right - left + 1
        result = 1
        for n in range(num):
            result = pow(self.w[right - n], result, self.m)
        return result


line = input().split(" ")
tower = Tower(int(line[0]), int(line[1]))
line = input().split(" ")
for item in line:
    tower.add_w(int(item))
q = int(input())
for i in range(q):
    line = input().split(" ")
    print(tower.ask(int(line[0]) - 1, int(line[1]) - 1))
