#include <bits/stdc++.h>
using namespace std;
const int iinf = 1e9 + 7;
const long long linf = 1ll << 60;
const double dinf = 1e60;
template <typename T>
inline void scf(T &x) {
  bool f = 0;
  x = 0;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  if (f) x = -x;
  return;
}
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) {
  scf(x);
  return scf(y);
}
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) {
  scf(x);
  scf(y);
  return scf(z);
}
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
  scf(x);
  scf(y);
  scf(z);
  return scf(w);
}
inline char mygetchar() {
  char c = getchar();
  while (c == ' ' || c == '\n') c = getchar();
  return c;
}
template <typename T>
void chkmax(T &x, const T &y) {
  if (y > x) x = y;
  return;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
  return;
}
const int N = 3e4 + 100;
const int B = 180;
int n, mod, m, q_n;
map<int, int> M;
int a[N], cnt[N], fib[N], bel[N], ans[N], RM[N];
struct node {
  node *ch[2];
  int siz, sum[2];
} * root;
pair<int, pair<int, int> > pls(const node *a, const node *b) {
  pair<int, pair<int, int> > ret;
  if (!b) {
    ret = make_pair(a->siz, make_pair(a->sum[0], a->sum[1]));
    return ret;
  }
  if (!a || !a->siz) {
    ret = make_pair(b->siz, make_pair(b->sum[0], b->sum[1]));
    return ret;
  }
  ret.first = a->siz + b->siz;
  ret.second.first =
      a->sum[0] + fib[a->siz] * b->sum[1] + fib[a->siz - 1] * b->sum[0];
  ret.second.second =
      a->sum[1] + fib[a->siz + 1] * b->sum[1] + fib[a->siz] * b->sum[0];
  return ret;
}
void build(node *&cur = root, int l = 0, int r = m) {
  cur = new node;
  cur->ch[0] = cur->ch[1] = 0;
  cur->siz = 0;
  cur->sum[0] = cur->sum[1] = 0;
  if (l == r) return;
  int mid = l + r >> 1;
  build(cur->ch[0], l, mid);
  build(cur->ch[1], mid + 1, r);
  return;
}
void modify(int i, int x, node *&cur = root, int l = 0, int r = m) {
  if (l == r) {
    if (x) {
      cur->siz = 1;
      cur->sum[0] = 0;
      cur->sum[1] = RM[i] % mod;
      return;
    }
    cur->siz = 0;
    cur->sum[0] = cur->sum[1] = 0;
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid)
    modify(i, x, cur->ch[0], l, mid);
  else
    modify(i, x, cur->ch[1], mid + 1, r);
  auto t = pls(cur->ch[0], cur->ch[1]);
  cur->siz = t.first;
  cur->sum[0] = t.second.first % mod;
  cur->sum[1] = t.second.second % mod;
  return;
}
struct query {
  int l, r, id;
  void in(int i) {
    scf(l, r);
    id = i;
  }
  bool operator<(const query &a) const {
    return bel[l] == bel[a.l] ? ((bel[l] & 1) ? r > a.r : r < a.r)
                              : bel[l] < bel[a.l];
  }
} q[N];
void TZL() {
  scf(n, mod);
  for (int i = (1); i <= (n); ++i) scf(a[i]), M[a[i]];
  fib[0] = 0;
  fib[1] = 1;
  for (int i = (2); i <= (n + 10); ++i) {
    fib[i] = fib[i - 1] + fib[i - 2];
    if (fib[i] >= mod) fib[i] -= mod;
  }
  for (int i = (1); i <= (n); ++i) bel[i] = i / B;
  for (auto it = M.begin(); it != M.end(); it++)
    it->second = (++m), RM[m] = it->first;
  M[0] = 0;
  build();
  return;
}
void ins(int x) {
  if (!cnt[x]++) modify(x, 1);
}
void del(int x) {
  if (!--cnt[x]) modify(x, 0);
}
void RANK1() {
  scf(q_n);
  for (int i = (1); i <= (q_n); ++i) q[i].in(i);
  sort(q + 1, q + q_n + 1);
  int l, r;
  l = r = 0;
  for (int i = (1); i <= (q_n); ++i) {
    int &lb = q[i].l, &rb = q[i].r;
    while (r < rb) ins(M[a[++r]]);
    while (r > rb) del(M[a[r--]]);
    while (l < lb) del(M[a[l++]]);
    while (l > lb) ins(M[a[--l]]);
    ans[q[i].id] = root->sum[1];
  }
  for (int i = (1); i <= (q_n); ++i) printf("%d\n", ans[i]);
  return;
}
int main() {
  TZL();
  RANK1();
  return 0;
}
