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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DPowerTower solver = new DPowerTower();
        solver.solve(1, in, out);
        out.close();
    }

    static class DPowerTower {
        int[] ar;
        int[] temp;
        int pos;

        public int phi(int n) {
            int phi = n;
            for (int i = 2; 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 long pow(long x, long y, long mod) {
            long res = 1;
            x = x % mod;
            while (y > 0) {
                if ((y & 1) == 1) res = res * x % mod;
                x = x * x % mod;
                y >>= 1;
            }
            return res;
        }

        public long limit(long x, long y, long limit) {
            long res = 1;
            while (y > 0) {
                if ((y & 1) == 1) {
                    res = res * x;
                    if (res >= limit) res = limit;
                }
                x = x * x;
                if (x >= limit) x = limit;
                y >>= 1;
            }
            return res;
        }

        public long test(int l, int r) {
            if (l == r) return ar[l];
            if (ar[l] == 1) return 1;
            return limit(ar[l], test(l + 1, r), 32);
        }

        public long get(int l, int r, int idx) {
            if (l == r || temp[idx] == 1) return ar[l] % temp[idx];
            long test = test(l + 1, Math.min(r, l + 6));
            if (test <= 30) {
                long ans = 1;
                for (int i = 1; i <= test; i++) ans = (ans * ar[l]) % temp[idx];
                return ans;
            }
            return pow(ar[l], get(l + 1, r, idx + 1) + temp[idx + 1], temp[idx]);
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int m = in.scanInt();
            ar = new int[n];
            temp = new int[100];
            pos = 0;
            temp[pos++] = m;
            while (temp[pos - 1] > 1) {
                temp[pos] = phi(temp[pos - 1]);
                pos++;
            }
            for (int i = 0; i < n; i++) ar[i] = in.scanInt();
            int q = in.scanInt();
            while (q-- > 0) {
                int l = in.scanInt() - 1;
                int r = in.scanInt() - 1;
                out.println(get(l, r, 0));
            }
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}