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
#include <bits/stdc++.h>
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
using namespace std;
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &a : v) is >> a;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (const T &t : v) os << t << " ";
  return os << endl;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &v) {
  return os << v.first << " " << v.second;
}
double gcd(double a, double b) { return a < 0.01 ? b : gcd(fmod(b, a), a); }
vector<long long int> parent, rak;
void make_set(long long int f) {
  for (long long i = 0; i < f + 1; i++) parent.push_back(i);
  rak.assign(f + 1, 1);
}
long long int find_set(long long int v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
long long int union_sets(long long int a, long long int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (rak[a] < rak[b]) swap(a, b);
    parent[b] = a;
    rak[a] += rak[b];
    return (rak[a] - rak[b]) * (rak[b]);
  }
  return 0;
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
long long bpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long int extend_gcd(long long int a, long long int b, long long int &x,
                         long long int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long int x1, y1;
  long long int ans = extend_gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return ans;
}
long long int inverse(long long int a, long long int m) {
  long long int x, y;
  extend_gcd(m, a, x, y);
  y %= m;
  y += m;
  y %= m;
  return y;
}
unsigned long long fhash(vector<long long int> p, long long int len) {
  unsigned long long h = 0xcbf29ce484222325ULL;
  for (long long int i = 0; i < len; i++) h = (h ^ p[i]) * 0x100000001b3ULL;
  return h;
}
long long int kv;
long long int t, n, x, y, h, k, z, p, q, w;
string s, s2, s1;
vector<long long int> m;
long long int phi(long long int a) {
  long long int ans = a;
  for (int i = 2; i * i <= a; i++) {
    if (a % i == 0) {
      while (a % i == 0) a /= i;
      ans -= ans / i;
    }
  }
  if (a > 1) ans -= ans / a;
  return ans;
}
long long int bow(long long a, long long b, long long m) {
  long long res = 1;
  while (b > 0) {
    if (b & 1)
      if (a >= m) return 1;
    res = res * a;
    if (res >= m) return 1;
    a = a * a;
    b >>= 1;
  }
  return 0;
}
long long int modulo(long long int a, long long int b) {
  if (a < b)
    return a;
  else
    return a % b + b;
}
vector<long long int> v;
long long int sg(long long int l, long long int r, long long int g) {
  if (l > r || g >= (long long int)m.size()) return 1;
  p = sg(l + 1, r, g + 1);
  q = m[g];
  kv = 1;
  z = v[l - 1];
  while (p) {
    if (p & 1) kv = modulo(kv * z, q);
    z = modulo(z * z, q);
    p >>= 1;
  }
  return kv;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  v.resize(n);
  cin >> v;
  m.push_back(k);
  while (m.back() != 1) m.push_back(phi(m.back()));
  cin >> t;
  while (t--) {
    cin >> x >> y;
    cout << sg(x, y, 0) % k << endl;
  }
  return 0;
}
