#include <bits/stdc++.h>
using namespace std;
const int max_n = 100005;
int n, mod;
int a[max_n];
int q;
unordered_map<int, int> phi;
long long quick_pow(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a < mod ? res * a : res * a % mod + mod;
    b >>= 1;
    a = a * a < mod ? a * a : a * a % mod + mod;
  }
  return res;
}
int Phi(int n) {
  if (phi[n]) return phi[n];
  int res = n, x = n;
  for (int i = 2; i <= sqrt(x); i++) {
    if (x % i == 0) {
      while (x % i == 0) x /= i;
      res = res / i * (i - 1);
    }
  }
  if (x != 1) res = res / x * (x - 1);
  return phi[n] = res;
}
long long solve(int l, int r, long long mod) {
  if (l == r || mod == 1) return a[l] < mod ? a[l] : a[l] % mod + mod;
  return quick_pow(a[l], solve(l + 1, r, Phi(mod)), mod);
}
int main() {
  scanf("%d%d", &n, &mod);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  scanf("%d", &q);
  int l, r;
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &l, &r);
    printf("%lld\n", solve(l, r, mod) % mod);
  }
  return 0;
}
