#include <bits/stdc++.h>
using namespace std;
vector<int> w;
vector<int> primes;
vector<int> isComposite;
void sieve(int N) {
  isComposite.assign(N + 1, 0);
  isComposite[0] = isComposite[1] = 1;
  for (int i = 2; i <= N; ++i)
    if (isComposite[i] == 0) {
      primes.push_back(i);
      if (1ll * i * i <= N)
        for (int j = i * i; j <= N; j += i) isComposite[j] = 1;
    }
}
int phi(int N) {
  int ans = N, idx = 0, p = primes[0];
  while (1ll * p * p <= N) {
    if (N % p == 0) ans -= ans / p;
    while (N % p == 0) N /= p;
    p = primes[++idx];
  }
  if (N != 1) ans -= ans / N;
  return ans;
}
int modPow(long long a, int e, int mod) {
  long long ans = 1;
  while (e > 0) {
    if ((e & 1) != 0) {
      if (1ll * ans * a >= mod)
        ans = (ans * a) % mod + mod;
      else
        ans = ans * a;
    }
    if (1ll * a * a >= mod)
      a = (int)((1ll * a * a) % mod + mod);
    else
      a = a * a;
    e >>= 1;
  }
  return (int)ans;
}
int tower(int mod, int l, int r) {
  if (mod == 1 || l == r) return w[l];
  int x = tower(phi(mod), l + 1, r);
  return modPow(w[l], x, mod);
}
bool overflow = false;
int modPowCheck(long long a, long long e, long long mod) {
  long long ans = 1;
  while (!overflow && e > 0) {
    if ((e & 1) != 0) {
      if (ans >= 1e9 / a) overflow = true;
      ans = (ans * a);
    }
    if (a >= 1e9 / a) overflow = true;
    a = (a * a);
    e >>= 1;
  }
  return (int)ans;
}
int canOverflow(int l, int r, int mod) {
  if (l == r || mod == 1 || overflow) return w[l];
  return modPowCheck(w[l], canOverflow(l + 1, r, phi(mod)), mod);
}
int main() {
  ios_base ::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  sieve(int(1e7));
  int n, m;
  cin >> n >> m;
  w.assign(n + 1, 0);
  for (int i = 1; i <= n; i++) cin >> w[i];
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    if (l == r)
      cout << w[l] % m << '\n';
    else {
      overflow = false;
      int x = canOverflow(l, r, m);
      if (overflow)
        cout << tower(m, l, r) % m << '\n';
      else
        cout << x % m << '\n';
    }
  }
  return 0;
}
