#include <bits/stdc++.h>
using namespace std;
const int maxn = 30010;
int p;
int fi[maxn];
inline int f(int x) {
  if (x >= 0)
    return fi[x];
  else
    return ((-x) & 1) ? fi[-x] : p - fi[-x];
}
struct Segment_Tree {
  int sum1[maxn << 2], sum2[maxn << 2];
  int size[maxn << 2];
  int tag_k[maxn << 2];
  int n;
  void Update(int o) {
    sum1[o] = (sum1[(o << 1)] + sum1[(o << 1 | 1)]) % p;
    sum2[o] = (sum2[(o << 1)] + sum2[(o << 1 | 1)]) % p;
    size[o] = size[(o << 1)] + size[(o << 1 | 1)];
  }
  void Mark(int o, int k) {
    if (k == 1) {
      int x1 = sum1[o];
      sum1[o] += sum2[o], sum2[o] = x1;
      if (sum1[o] > p) sum1[o] -= p;
      tag_k[o]++;
      return;
    }
    int x1 = (sum1[o] * f(k + 1) + sum2[o] * f(k)) % p,
        x2 = (sum1[o] * f(k) + sum2[o] * f(k - 1)) % p;
    sum1[o] = x1;
    sum2[o] = x2;
    tag_k[o] += k;
  }
  void Push_Down(int o) {
    if (tag_k[o]) {
      Mark((o << 1), tag_k[o]);
      Mark((o << 1 | 1), tag_k[o]);
      tag_k[o] = 0;
    }
  }
  void Change(int o, int l, int r, int x, int v, int w, int c) {
    if (l == r) {
      if (c == -1)
        size[o] = sum1[o] = sum2[o] = 0;
      else
        size[o] = 1, sum1[o] = v * f(w + 1) % p, sum2[o] = v * f(w) % p;
      return;
    }
    Push_Down(o);
    if (x <= ((l + r) >> 1))
      Change((o << 1), l, ((l + r) >> 1), x, v, w, c), Mark((o << 1 | 1), c);
    else
      Change((o << 1 | 1), ((l + r) >> 1) + 1, r, x, v, w + size[(o << 1)], c);
    Update(o);
  }
  void Change(int x, int v, int c) { Change(1, 1, n, x, v, 0, c); }
  int Result() { return sum1[1]; }
} T;
int a[maxn], temp[maxn];
int cnt[maxn];
int ans[maxn];
int n, q, blocksize, ts;
struct Query {
  int l, r, block, id;
  bool operator<(const Query &b) const {
    return block < b.block || block == b.block && r < b.r;
  }
} Q[maxn];
int main() {
  scanf("%d%d", &n, &p);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memcpy(temp, a, sizeof(temp));
  sort(temp + 1, temp + 1 + n);
  ts = unique(temp + 1, temp + 1 + n) - (temp + 1);
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(temp + 1, temp + 1 + ts, a[i]) - temp;
  for (int i = 1; i <= ts; i++) temp[i] %= p;
  T.n = ts;
  fi[1] = 1;
  fi[2] = 1;
  for (int i = 3; i <= ts + 2; i++) fi[i] = (fi[i - 1] + fi[i - 2]) % p;
  blocksize = sqrt(n);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++)
    scanf("%d%d", &Q[i].l, &Q[i].r), Q[i].block = Q[i].l / blocksize,
                                     Q[i].id = i;
  sort(Q + 1, Q + 1 + q);
  for (int i = 1, l = 1, r = 0; i <= q; i++) {
    while (r < Q[i].r) {
      r++;
      cnt[a[r]]++;
      if (cnt[a[r]] == 1) T.Change(a[r], temp[a[r]], 1);
    }
    while (r > Q[i].r) {
      cnt[a[r]]--;
      if (cnt[a[r]] == 0) T.Change(a[r], temp[a[r]], -1);
      r--;
    }
    while (l > Q[i].l) {
      l--;
      cnt[a[l]]++;
      if (cnt[a[l]] == 1) T.Change(a[l], temp[a[l]], 1);
    }
    while (l < Q[i].l) {
      cnt[a[l]]--;
      if (cnt[a[l]] == 0) T.Change(a[l], temp[a[l]], -1);
      l++;
    }
    ans[Q[i].id] = T.Result();
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}
