#include <bits/stdc++.h>
using namespace std;
int n, mod;
inline int add(int a, int b) {
  if ((a += b) >= mod) a -= mod;
  return a;
}
inline int dec(int a, int b) {
  if ((a -= b) < 0) a += mod;
  return a;
}
inline int mult(int a, int b) {
  long long t = 1ll * a * b;
  if (t >= mod) t %= mod;
  return t;
}
int F[30010], val[30010], a[30010], pt[30010], End;
class sgt {
 public:
  int sum[120010][2], cnt[120010];
  void pushup(int p) {
    cnt[p] = cnt[(p << 1)] + cnt[((p << 1) | 1)];
    if (cnt[(p << 1)]) {
      sum[p][0] = add(add(mult(F[cnt[(p << 1)] - 1], sum[((p << 1) | 1)][0]),
                          mult(F[cnt[(p << 1)]], sum[((p << 1) | 1)][1])),
                      sum[(p << 1)][0]);
      sum[p][1] = add(add(mult(F[cnt[(p << 1)]], sum[((p << 1) | 1)][0]),
                          mult(F[cnt[(p << 1)] + 1], sum[((p << 1) | 1)][1])),
                      sum[(p << 1)][1]);
    } else {
      sum[p][0] = sum[((p << 1) | 1)][0];
      sum[p][1] = sum[((p << 1) | 1)][1];
    }
  }
  inline void modify(int pos, int v) {
    int l = 1, r = End, p = 1;
    while (l ^ r) {
      int mid = (l + r) >> 1;
      if (pos <= mid)
        p <<= 1, r = mid;
      else
        p = (p << 1) | 1, l = mid + 1;
    }
    if (v) {
      sum[p][0] = sum[p][1] = val[l];
      cnt[p] = 1;
    } else {
      sum[p][0] = sum[p][1] = 0;
      cnt[p] = 0;
    }
    while (p ^ 1) pushup(p >>= 1);
  }
} T;
inline void Add(int v) {
  if (!pt[v]) T.modify(v, 1);
  ++pt[v];
}
inline void Del(int v) {
  --pt[v];
  if (!pt[v]) T.modify(v, 0);
}
const int blk = 200;
class query {
 public:
  int l, r, id;
  bool operator<(const query &t) const {
    if (l / blk != t.l / blk) return l / blk < t.l / blk;
    return r < t.r;
  }
} q[30010];
int Q, ans[30010];
int main() {
  scanf("%d%d", &n, &mod);
  F[1] = F[2] = 1;
  for (int i = 3; i <= 30001; i++) F[i] = add(F[i - 1], F[i - 2]);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), val[i] = a[i];
  sort(val + 1, val + n + 1);
  End = unique(val + 1, val + n + 1) - val - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(val + 1, val + End + 1, a[i]) - val;
  for (int i = 1; i <= End; i++) val[i] %= mod;
  scanf("%d", &Q);
  for (int T = 1; T <= Q; T++) {
    scanf("%d%d", &q[T].l, &q[T].r);
    q[T].id = T;
  }
  sort(q + 1, q + Q + 1);
  for (int i = 1, l = 1, r = 0; i <= Q; i++) {
    while (r < q[i].r) Add(a[++r]);
    while (l > q[i].l) Add(a[--l]);
    while (r > q[i].r) Del(a[r--]);
    while (l < q[i].l) Del(a[l++]);
    ans[q[i].id] = T.sum[1][0];
  }
  for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
  return 0;
}
