Problem: 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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <class Type>
inline void read(Type &cur) {
  Type ret = 0, flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    ret = ret * 10 + ch - '0';
    ch = getchar();
  }
  cur = ret * flag;
}
inline long long phi(long long x) {
  long long s = sqrt(x), ans = x;
  for (long long i = 2; i <= s; ++i) {
    if (x % i == 0) {
      ans = ans / i * (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x > 1) ans = ans / x * (x - 1);
  return ans;
}
const int N = 500005;
const int M = 20000005;
const int inf = N - 4;
const int lim = 20000000;
using namespace std;
int n, m, x;
long long c[N], a[N];
bool vis[M];
int las[N];
inline int read() {
  int f = 1, x = 0;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -1;
  } while (ch < '0' || ch > '9');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return f * x;
}
inline int fpow(int x, long long p, int yql) {
  int ans = 1;
  for (; p; p >>= 1, x = 1LL * x * x % yql)
    if (p & 1) ans = 1LL * ans * x % yql;
  return ans;
}
long long sumv[N << 2], addv[N << 2], fone[N << 2];
long long pf[N];
inline void pushup(int o) {
  sumv[o] = sumv[(o << 1)] + sumv[(o << 1 | 1)];
  fone[o] = min(fone[(o << 1)], fone[(o << 1 | 1)]);
}
inline void build(int o, int l, int r) {
  fone[o] = inf;
  if (l == r) {
    sumv[o] = a[l];
    if (a[l] == 1) fone[o] = l;
    return;
  }
  int mid = (l + r) >> 1;
  build((o << 1), l, mid);
  build((o << 1 | 1), mid + 1, r);
  pushup(o);
}
inline void pushdown(int o, int l, int r) {
  if (!addv[o]) return;
  int mid = (l + r) >> 1;
  addv[(o << 1)] += addv[o];
  addv[(o << 1 | 1)] += addv[o];
  sumv[(o << 1)] += addv[o] * 1LL * (mid - l + 1);
  sumv[(o << 1 | 1)] += addv[o] * 1LL * (r - mid);
  fone[(o << 1)] = inf;
  fone[(o << 1 | 1)] = inf;
  addv[o] = 0;
}
inline void change(int o, int l, int r, int q, int v) {
  if (l == r) {
    sumv[o] = v;
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(o, l, r);
  if (q <= mid)
    change((o << 1), l, mid, q, v);
  else
    change((o << 1 | 1), mid + 1, r, q, v);
  pushup(o);
}
inline void optadd(int o, int l, int r, int ql, int qr, int v) {
  if (ql <= l && r <= qr) {
    addv[o] += v;
    sumv[o] += 1LL * (r - l + 1) * v;
    fone[o] = inf;
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(o, l, r);
  if (ql <= mid) optadd((o << 1), l, mid, ql, qr, v);
  if (qr > mid) optadd((o << 1 | 1), mid + 1, r, ql, qr, v);
  pushup(o);
}
inline long long querysum(int o, int l, int r, int q) {
  if (l == r) return sumv[o];
  int mid = (l + r) >> 1;
  pushdown(o, l, r);
  if (q <= mid)
    return querysum((o << 1), l, mid, q);
  else
    return querysum((o << 1 | 1), mid + 1, r, q);
}
inline long long query(int q) {
  if (las[q] == m) return a[q];
  las[q] = m;
  return a[q] = querysum(1, 1, n, q);
}
inline int queryfst(int o, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return fone[o];
  int mid = (l + r) >> 1;
  pushdown(o, l, r);
  int ans = inf;
  if (ql <= mid) ans = min(ans, queryfst((o << 1), l, mid, ql, qr));
  if (qr > mid) ans = min(ans, queryfst((o << 1 | 1), mid + 1, r, ql, qr));
  return ans;
}
inline long long calc(int l, int r, int ff) {
  int yql = pf[ff];
  if (query(l) % yql == 0) return 0;
  if (yql == 1) return 1;
  if (l == r) return query(l) % yql + (query(l) >= yql) * yql;
  int f = min(r, l + 5);
  for (int i = l + 1; i <= f; i++)
    if (query(i) == 1) {
      f = i;
      break;
    }
  long long last = query(f), q = 0;
  for (int i = f - 1; i >= l + 1; i--) {
    q = last, last = 1;
    while (q--) {
      last *= query(i);
      if (last >= pf[ff + 1])
        return fpow(query(l) % yql, calc(l + 1, r, ff + 1) + pf[ff + 1], yql);
    }
  }
  return fpow(query(l) % yql, last, yql);
}
int main() {
  memset(las, -1, sizeof(las));
  n = read();
  int mo = 0;
  mo = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  int k = mo, cnt = 0;
  pf[++cnt] = mo;
  while (pf[cnt] - 1) ++cnt, pf[cnt] = phi(pf[cnt - 1]);
  pf[++cnt] = 1;
  build(1, 1, n);
  m = read();
  cerr << "cnt"
       << "=" << cnt << endl;
  while (m--) {
    int l = read(), r = read(), yql = mo;
    printf("%I64d\n", (calc(l, r, 1)) % yql);
  }
}