Problem: 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 wk then value of power of a new tower will be {wk}p. 

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

<image>

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 ≤ 105) and m (1 ≤ m ≤ 109).

Second line of input contains n integers wk (1 ≤ wk ≤ 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.

kth of next q lines contains two integers lk and rk (1 ≤ lk ≤ rk ≤ 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 lk, lk + 1, ..., rk.

Example

Input

6 1000000000
1 2 2 3 3 3
8
1 1
1 6
2 2
2 3
2 4
4 4
4 5
4 6


Output

1
1
2
4
256
3
27
597484987

Note

327 = 7625597484987

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;

public class F {

    private static int[] w;

    private static int fastModPow(int a, int b, int mod) {
        int modPow = 1;
        for (; b > 0; b >>= 1) {
            if ((b & 1) != 0)
                modPow = modMul(modPow, a, mod);
            a = modMul(a, a, mod);
        }
        return modPow;
    }

    private static int modMul(int a, int b, int mod) {
        return 1L * a * b >= mod ? (int) ((1L * a * b) % mod) + mod : a * b;
    }

    private static int phi(int n) {
        int phi = n;

        for (int i = 2; 1L * i*i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                phi -= phi / i;
            }
        }
        if (n > 1)
            phi -= phi / n;

        return phi;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String[] splits;

        splits = in.readLine().split(" ");
        int n = Integer.parseInt(splits[0]);
        int m = Integer.parseInt(splits[1]);

        w = new int[n];
        splits = in.readLine().split(" ");
        for (int i = 0; i < n; i++)
            w[i] = Integer.parseInt(splits[i]);

        ArrayList<Integer> phis = new ArrayList<>();
        for (
            phis.add(m);
            phis.get(phis.size() - 1) > 1;
            phis.add(phi(phis.get(phis.size() - 1)))
        );

        int q = Integer.parseInt(in.readLine());

        while (q-- > 0) {
            splits = in.readLine().split(" ");
            int l = Integer.parseInt(splits[0]) - 1;
            int r = Integer.parseInt(splits[1]) - 1;

            int answer = 1;
            for (int i = Math.min(r - l, phis.size() - 1); i >= 0; i--)
                answer = fastModPow(w[l + i], answer, phis.get(i));

            out.println(answer % m);
        }
        out.flush();
    }

}