#include <bits/stdc++.h>
using namespace std;
map<long long, long long> w;
long long a[((long long)(2e6 + 900))];
long long n, m;
long long q;
long long tot(long long x) {
  long long p = x;
  long long c = x;
  for (long long i = 2; i * i <= c; i++) {
    if (c % i == 0) {
      p /= i;
      p *= i - 1;
      while (c % i == 0) c /= i;
    }
  }
  if (c > 1) {
    p /= c;
    p *= c - 1;
  }
  return p;
}
long long mmod(long long x, long long m) {
  if (x >= m) return m + (x) % m;
  return x;
}
long long pw(long long a, long long b, long long m) {
  long long p = 1;
  while (b) {
    if (b & 1ll) p = mmod((p * a), m);
    a = mmod((a * a), m);
    b >>= 1ll;
  }
  return p;
}
long long get(long long l, long long r, long long m) {
  if (l == r) return mmod(a[l], m);
  if (m == 1) return 1;
  long long k = get(l + 1, r, w[m]);
  return pw(a[l], k, m);
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  long long k = m;
  while (k > 1) {
    w[k] = tot(k);
    k = w[k];
  }
  long long q, l, r;
  cin >> q;
  while (q--) {
    cin >> l >> r;
    l--;
    r--;
    cout << get(l, r, m) % m << endl;
  }
}
