#include <bits/stdc++.h>
using namespace std;
long long w[100010];
map<long long, long long> mp;
long long qpow(long long x, long long n, long long mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x < mod ? res * x : res * x % mod + mod, n--;
    x = x * x < mod ? x * x : x * x % mod + mod;
    n >>= 1;
  }
  return res;
}
long long phi(long long m) {
  long long s = m;
  if (mp.count(m)) return mp[m];
  for (long long i = 2; i * i <= m; i++) {
    if (m % i == 0) s = s / i * (i - 1);
    while (m % i == 0) m /= i;
  }
  if (m > 1) s = s / m * (m - 1);
  mp[m] = s;
  return s;
}
long long solve(long long l, long long r, long long m) {
  if (l == r || m == 1) {
    if (w[l] < m)
      return w[l];
    else
      return ((w[l] % m) + m);
  }
  return qpow(w[l], solve(l + 1, r, phi(m)), m);
}
int main() {
  long long n, m, q;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> w[i];
  cin >> q;
  while (q > 0) {
    int l, r;
    cin >> l >> r;
    cout << solve(l, r, m) % m << endl;
    q--;
  }
  return 0;
}
