#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[30005], tmp[30005];
int B;
struct query {
  int l, r, id;
  bool operator<(const query &x) const {
    if (l / B != x.l / B) return l < x.l;
    return (l / B) & 1 ? r < x.r : r > x.r;
  }
} q[30005];
struct matrix {
  int a, b, c, d;
  void set() {
    a = d = 1;
    b = c = 0;
  }
  void operator*(const matrix &w) {
    matrix s;
    s.a = (a * w.a + b * w.c) % m;
    s.b = (a * w.b + b * w.d) % m;
    s.c = (c * w.a + d * w.c) % m;
    s.d = (c * w.b + d * w.d) % m;
    a = s.a;
    b = s.b;
    c = s.c;
    d = s.d;
  }
} zy, nzy, ad[30005 << 2], sum[30005 << 2];
int f[30005], vis[30005 << 2];
int ss[30005];
int lb(int x) { return x & (-x); }
void adds(int x, int y) {
  for (; x <= n; x += lb(x)) ss[x] += y;
}
int ask(int x) {
  int ans = 0;
  for (; x; x -= lb(x)) ans += ss[x];
  return ans;
}
void build(int k, int l, int r) {
  ad[k].set();
  if (l == r) return;
  int mid = l + r >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
}
void add(int k, const matrix &w) {
  ad[k] * w;
  sum[k] * w;
  vis[k] = 1;
}
void pd(int k) {
  if (!vis[k]) return;
  add(k << 1, ad[k]);
  add(k << 1 | 1, ad[k]);
  ad[k].set();
  vis[k] = 0;
}
void update(int k) {
  sum[k].a = (sum[k << 1].a + sum[k << 1 | 1].a) % m;
  sum[k].b = (sum[k << 1].b + sum[k << 1 | 1].b) % m;
}
void change(int k, int l, int r, int a, int x, int y, int op) {
  sum[k].a += op * x + m;
  sum[k].b += op * y + m;
  sum[k].a %= m;
  sum[k].b %= m;
  if (l == r) return;
  pd(k);
  int mid = l + r >> 1;
  if (a <= mid)
    change(k << 1, l, mid, a, x, y, op);
  else
    change(k << 1 | 1, mid + 1, r, a, x, y, op);
}
void change(int k, int l, int r, int x, int y, const matrix &a) {
  if (x > y) return;
  if (x <= l && r <= y) return add(k, a);
  pd(k);
  int mid = l + r >> 1;
  if (x <= mid) change(k << 1, l, mid, x, y, a);
  if (mid < y) change(k << 1 | 1, mid + 1, r, x, y, a);
  update(k);
}
int t[30005];
void add(int x) {
  t[a[x]]++;
  if (t[a[x]] == 1) {
    adds(a[x], 1);
    int s = ask(a[x]);
    change(1, 1, n, a[x], f[s - 1] * tmp[a[x]] % m, f[s] * tmp[a[x]] % m, 1);
    change(1, 1, n, a[x] + 1, n, zy);
  }
}
void erase(int x) {
  t[a[x]]--;
  if (t[a[x]] == 0) {
    change(1, 1, n, a[x] + 1, n, nzy);
    int s = ask(a[x]);
    change(1, 1, n, a[x], f[s - 1] * tmp[a[x]] % m, f[s] * tmp[a[x]] % m, -1);
    adds(a[x], -1);
  }
}
int res[30005];
signed main() {
  zy.b = zy.c = zy.d = 1;
  scanf("%d%d", &n, &m);
  nzy.b = nzy.c = 1;
  nzy.a = m - 1;
  f[1] = 1;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), tmp[i] = a[i];
  for (int i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % m;
  sort(tmp + 1, tmp + n + 1);
  int sss = unique(tmp + 1, tmp + n + 1) - tmp - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(tmp + 1, tmp + sss + 1, a[i]) - tmp;
  for (int i = 1; i <= n; i++) tmp[i] %= m;
  int Q;
  scanf("%d", &Q);
  for (int i = 1; i <= Q; i++) {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  B = sqrt(n);
  sort(q + 1, q + Q + 1);
  int l = 1, r = 0;
  build(1, 1, n);
  for (int i = 1; i <= Q; i++) {
    while (r < q[i].r) add(++r);
    while (l > q[i].l) add(--l);
    while (r > q[i].r) erase(r--);
    while (l < q[i].l) erase(l++);
    res[q[i].id] = sum[1].b;
  }
  for (int i = 1; i <= Q; i++) cout << res[i] << "\n";
  return 0;
}
