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>
using namespace std;
const long double EPS = 1e-10;
const long long MOD = 1e9 + 7;
const long double PI = 3.1415926535897932384626433832795028841;
ostream& operator<<(std::ostream& stream, const long long* arr) {
  int i = 0;
  cout << "{";
  while (arr[i] != INT_MAX) {
    cout << arr[i];
    if (arr[i + 1] != INT_MAX) cout << ",";
    i++;
  }
  cout << "}";
  return stream;
}
ostream& operator<<(std::ostream& stream, const vector<int> vec) {
  cout << "{";
  for (int i = 0; i < vec.size(); i++) {
    cout << vec[i];
    if (i != vec.size() - 1) cout << ",";
  }
  cout << "}";
  return stream;
}
ostream& operator<<(std::ostream& stream,
                    const pair<long long, long long>& vec) {
  cout << "(" << vec.first << ',' << vec.second << ")";
  return stream;
}
template <class T>
struct segtree_t {
  vector<T> t, lazy, flag_equal;
  int st, sz;
  T (*addition_fun)(T, T);
  T invalid_value;
  segtree_t() {}
  segtree_t(int start, int finish, T* arr, T (*add_fun)(T, T), T invalid_val) {
    int size = (finish + 1) * 2;
    int tree_size = 2;
    while (tree_size < size) tree_size *= 2;
    t = vector<T>(tree_size);
    lazy = vector<T>(tree_size);
    flag_equal = vector<T>(tree_size);
    st = start;
    sz = finish;
    addition_fun = add_fun;
    invalid_value = invalid_val;
    build(1, start, finish, arr);
  }
  void build(int i, int l, int r, T* arr) {
    if (l > r) return;
    lazy[i] = 0;
    flag_equal[i] = 0;
    if (l == r) {
      t[i] = arr[l];
    } else {
      build(i * 2, l, (l + r) / 2, arr);
      build(i * 2 + 1, (l + r) / 2 + 1, r, arr);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  void inc_range(int l, int r, T value) {
    if (l > r) return;
    inc_range_rec(1, st, sz, l, r, value);
  }
  void set_values(int l, int r, T value) {
    set_values_rec(1, st, sz, l, r, value);
  }
  void inc_range_rec(int i, int l, int r, int tl, int tr, T value) {
    if (lazy[i] != 0) {
      t[i] += lazy[i];
      if (l != r) {
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
      }
      lazy[i] = 0;
    }
    if (r < tl or l > tr) return;
    if (l > r) return;
    if (l >= tl and r <= tr) {
      if (l != r) {
        lazy[i * 2] += value;
        lazy[i * 2 + 1] += value;
      }
      t[i] += value;
    } else {
      inc_range_rec(i * 2, l, (l + r) / 2, tl, tr, value);
      inc_range_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr, value);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  T query_rec(int i, int l, int r, int tl, int tr) {
    if (flag_equal[i] != 0) {
      if (l != r) {
        t[i * 2] = t[i];
        t[i * 2 + 1] = t[i];
        flag_equal[i * 2] = 1;
        flag_equal[i * 2 + 1] = 1;
      }
      flag_equal[i] = 0;
    }
    if (r < tl or l > tr) return invalid_value;
    if (l > r) return invalid_value;
    if (lazy[i] != 0) {
      t[i] += lazy[i];
      if (l != r) {
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
      }
      lazy[i] = 0;
    }
    if (l >= tl and r <= tr) {
      return t[i];
    } else {
      T m1 = query_rec(i * 2, l, (l + r) / 2, tl, tr);
      T m2 = query_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr);
      if (m1 == invalid_value && m2 == invalid_value) return invalid_value;
      if (m1 == invalid_value) return m2;
      if (m2 == invalid_value) return m1;
      return addition_fun(m1, m2);
    }
  }
  T query(int l, int r) { return query_rec(1, st, sz, l, r); }
  void set_values_rec(int i, int l, int r, int tl, int tr, T value) {
    if (flag_equal[i] != 0) {
      if (l != r) {
        t[i * 2] = t[i];
        t[i * 2 + 1] = t[i];
        flag_equal[i * 2] = 1;
        flag_equal[i * 2 + 1] = 1;
      }
      flag_equal[i] = 0;
    }
    if (r < tl || l > tr) return;
    if (l > r) return;
    if (l >= tl and r <= tr) {
      t[i] = value;
      flag_equal[i] = 1;
    } else {
      set_values_rec(i * 2, l, (l + r) / 2, tl, tr, value);
      set_values_rec(i * 2 + 1, (l + r) / 2 + 1, r, tl, tr, value);
      t[i] = addition_fun(t[i * 2], t[i * 2 + 1]);
    }
  }
  ~segtree_t() {}
};
template <class T>
struct fenwick_t {
  vector<T> FW;
  fenwick_t(int n) { FW = vector<T>(n + 1); }
  void inc(int i, T v) {
    while (i <= FW.size() - 1) {
      FW[i] += v;
      i += i & (-i);
    }
  }
  T get(int i) {
    T rta = 0;
    while (i > 0) {
      rta += FW[i];
      i -= i & (-i);
    }
    return rta;
  }
};
const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;
const int maxk = 1e5 + 5;
const int maxq = 1e5 + 5;
long long powmod(long long a, long long b, long long m, int* flag) {
  *flag = 0;
  if (b == 0) {
    return 1;
  }
  if (b == 1) {
    *flag = a >= m;
    return a % m;
  }
  long long res = 1;
  if (a >= m) *flag = 1;
  a %= m;
  for (; b; b >>= 1) {
    if (b & 1) {
      if (res * a >= m) *flag = 1;
      res = res * a % m;
    }
    if (a * a >= m) *flag = 1;
    a = a * a % m;
  }
  return res;
}
long long w[maxn];
long long tots[maxn];
int cnt = 0;
long long tot(long long n) {
  if (n == 1) return 1;
  long long sum = n;
  long long m = sqrt(n + 0.5);
  for (long long i = 2; i <= m; i++) {
    if (!(n % i)) {
      sum = sum * (i - 1) / i;
      while (!(n % i)) n /= i;
    }
  }
  if (n > 1) sum = sum / n * (n - 1);
  return sum;
}
long long query(int l, int r, long long m, int lvl, int* flag) {
  if (m == 1) {
    *flag = 1;
    return 0;
  }
  if (l == r) {
    *flag = w[l] >= m;
    return w[l] % m;
  }
  long long phi_m = lvl >= cnt ? 1 : tots[lvl];
  int aux = 0;
  long long x = query(l + 1, r, phi_m, lvl + 1, &aux);
  if (!aux) {
    return powmod(w[l], x, m, flag);
  } else {
    return powmod(w[l], x + phi_m, m, flag);
  }
}
int main() {
  int fg;
  long long n, m;
  scanf("%lld%lld", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
  long long val = m;
  while (val > 1) {
    val = tot(val);
    tots[cnt++] = val;
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    int aux = 0;
    printf("%lld", query(l, r, m, 0, &aux));
    printf("\n");
  }
}