#include <bits/stdc++.h>
using namespace std;
const int maxn = 30005;
const int inf = 0x3f3f3f3f;
int mod;
int a[maxn], w[maxn], ans[maxn];
int cnt[maxn], tot;
int fib[maxn];
struct qNode {
  int l, r, id, part;
  bool operator<(const qNode &x) const {
    if (part == x.part) return r < x.r;
    return part < x.part;
  }
} q[maxn];
struct TNode {
  long long pre;
  long long now;
  int sz;
} tree[maxn * 4];
void pushup(int p) {
  int ls = p * 2, rs = p * 2 + 1;
  int k = tree[ls].sz;
  tree[p].sz = tree[ls].sz + tree[rs].sz;
  tree[p].pre = tree[ls].pre + tree[rs].pre * (k > 0 ? fib[k - 1] : 1) +
                tree[rs].now * fib[k];
  tree[p].pre %= mod;
  tree[p].now =
      tree[ls].now + tree[rs].pre * fib[k] + tree[rs].now * fib[k + 1];
  tree[p].now %= mod;
}
void build(int p, int l, int r) {
  if (l == r)
    tree[p] = TNode{0, 0, 0};
  else {
    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    tree[p] = TNode{0, 0, 0};
  }
}
void update(int p, int l, int r, int id, int v) {
  if (l == r) {
    tree[p].now += v * w[id];
    tree[p].sz += v;
    return;
  }
  int mid = (l + r) >> 1;
  if (id <= mid) update(p * 2, l, mid, id, v);
  if (id > mid) update(p * 2 + 1, mid + 1, r, id, v);
  pushup(p);
}
void modify(int idx, int v) {
  int x = a[idx];
  cnt[x] += v;
  if (cnt[x] == 1 && v == 1) {
    update(1, 1, tot, x, 1);
  }
  if (cnt[x] == 0) {
    update(1, 1, tot, x, -1);
  }
}
int main() {
  int n;
  scanf("%d%d", &n, &mod);
  map<int, int> rak;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    rak[a[i]] = 1;
  }
  tot = 0;
  for (auto it : rak) {
    rak[it.first] = ++tot;
    w[tot] = it.first;
  }
  for (int i = 1; i <= n; i++) {
    a[i] = rak[a[i]];
  }
  fib[0] = 0;
  fib[1] = 1;
  for (int i = 2; i <= tot + 1; i++) {
    fib[i] = (fib[i - 2] + fib[i - 1]) % mod;
  }
  int qCase;
  scanf("%d", &qCase);
  int block = sqrt(n);
  for (int i = 1; i <= qCase; i++) {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
    q[i].part = (q[i].l - 1) / block + 1;
  }
  sort(q + 1, q + 1 + qCase);
  int l = 1, r = 0;
  build(1, 1, tot);
  for (int i = 1; i <= qCase; i++) {
    while (l > q[i].l) modify(--l, 1);
    while (r < q[i].r) modify(++r, 1);
    while (l < q[i].l) modify(l++, -1);
    while (r > q[i].r) modify(r--, -1);
    ans[q[i].id] = tree[1].now;
  }
  for (int i = 1; i <= qCase; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
