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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
unsigned long long gcd(unsigned long long a, unsigned long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
unsigned long long mult(unsigned long long a, unsigned long long b,
                        unsigned long long M) {
  if (b == 1) return a;
  if ((b & 1) == 0) {
    unsigned long long t = mult(a, b / 2, M);
    return (2 * t) % M;
  }
  return (mult(a, b - 1, M) + a) % M;
}
unsigned long long binpow(unsigned long long X, unsigned long long P,
                          unsigned long long M) {
  unsigned long long R = 1;
  unsigned long long XM = X % M;
  while (P) {
    if (P & 1) {
      R = (R * XM) % M;
    }
    XM = (XM * XM) % M;
    P >>= 1;
  }
  return R;
}
int fermat(unsigned long long n) {
  if (n == 2) return 1;
  for (int i = 0; i < 100; i++) {
    unsigned long long x = (rand() % (n - 2)) + 2;
    unsigned long long g = gcd(x, n);
    unsigned long long b = binpow(x, n - 1, n);
    if (g != 1) return 0;
    if (b != 1) return 0;
  }
  return 1;
}
void factor(unsigned long long n, vector<unsigned long long> &factors) {
  unsigned long long N = n;
  while ((N % 2 == 0) && (N > 0)) {
    N /= 2;
    factors.push_back(2);
  }
  while ((N % 3 == 0) && (N > 0)) {
    N /= 3;
    factors.push_back(3);
  }
  while ((N % 5 == 0) && (N > 0)) {
    N /= 5;
    factors.push_back(5);
  }
  while (N > 1) {
    if (fermat(N)) {
      factors.push_back(N);
      return;
    }
    for (unsigned long long k = 1; 6 * k - 1 <= N; k++) {
      unsigned long long x1 = 6 * k - 1, x2 = 6 * k + 1;
      int f = 0;
      while (N % x1 == 0) {
        N /= x1;
        factors.push_back(x1);
        f = 1;
      }
      while (N % x2 == 0) {
        N /= x2;
        factors.push_back(x2);
        f = 1;
      }
      if (f) break;
    }
  }
}
unsigned long long euler_phi(map<unsigned long long, unsigned long long> &phis,
                             unsigned long long n) {
  if (n == 1) return 1;
  if (phis[n] > 0) return phis[n];
  vector<unsigned long long> f;
  factor(n, f);
  int i = 0;
  int k = 0;
  unsigned long long prev = f[0];
  unsigned long long res = 1;
  while (i < f.size()) {
    if (f[i] == prev) {
      k++;
      i++;
      if (i == f.size()) res *= binpow(prev, k - 1, n) * (prev - 1);
      continue;
    }
    res *= binpow(prev, k - 1, n) * (prev - 1);
    k = 1;
    prev = f[i];
    i++;
    if (i == f.size()) res *= binpow(prev, k - 1, n) * (prev - 1);
  }
  return phis[n] = res;
}
unsigned long long calc(int *w, int l, int r, int m,
                        map<unsigned long long, unsigned long long> &phis) {
  if (l == r) {
    return (unsigned long long)w[l] % m;
  }
  if (l == r - 1) {
    return binpow(w[l], w[r], m);
  }
  if (m == 1) return 0;
  unsigned long long phi = euler_phi(phis, m);
  unsigned long long x = calc(w, l + 1, r, phi, phis);
  bool flag = false;
  unsigned long long t1 = 1;
  if ((((r >= l + 4) && (w[l + 4] == 1)) || (r == l + 3)) &&
      ((w[l + 3] <= 2) && (w[l + 2] <= 2) & (w[l + 1] <= 2))) {
    int p = 1;
    for (int k1 = 0; k1 < w[l + 3]; k1++) p *= w[l + 2];
    for (int k1 = 0; k1 < p; k1++) t1 *= w[l + 1];
    flag = true;
  } else if ((((r >= l + 3) && (w[l + 3] == 1)) || (r == l + 2)) &&
             ((w[l + 2] <= 3) && (w[l + 1] <= 4))) {
    for (int k1 = 0; k1 < w[l + 2]; k1++) t1 *= w[l + 1];
    flag = true;
  } else if ((w[l + 2] == 1) && (w[l + 1] <= 40)) {
    t1 = w[l + 1];
    flag = true;
  } else if (w[l + 1] == 1) {
    flag = true;
  }
  if (flag) {
    return binpow(w[l], t1, m);
  }
  unsigned long long t = binpow(w[l], phi + x, m);
  return t;
}
int main() {
  srand(time(NULL));
  int n, m;
  scanf("%d %d", &n, &m);
  int *w = new int[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &w[i]);
  }
  int q;
  scanf("%d", &q);
  map<unsigned long long, unsigned long long> phis;
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    l--;
    r--;
    cout << calc(w, l, r, m, phis) << endl;
  }
  delete[] w;
}