#include <bits/stdc++.h>
using namespace std;
template <typename T, typename S>
inline bool upmin(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool upmax(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
template <typename N, typename PN>
inline N flo(N a, PN b) {
  return a >= 0 ? a / b : -((-a - 1) / b) - 1;
}
template <typename N, typename PN>
inline N cei(N a, PN b) {
  return a > 0 ? (a - 1) / b + 1 : -(-a / b);
}
template <typename N>
N gcd(N a, N b) {
  return b ? gcd(b, a % b) : a;
}
inline void gn(long long& x) {
  int sg = 1;
  char c;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  c == '-' ? (sg = -1, x = 0) : (x = c - '0');
  while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
  x *= sg;
}
inline void gn(int& x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(unsigned long long& x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(double& x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline void gn(long double& x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline long long sqr(long long a) { return a * a; }
inline double sqrf(double a) { return a * a; }
int inf = 0x3f3f3f3f;
double eps = 1e-6;
int mo = 1000000007;
int qp(int a, long long b) {
  int n = 1;
  do {
    if (b & 1) n = 1ll * n * a % mo;
    a = 1ll * a * a % mo;
  } while (b >>= 1);
  return n;
}
int first[33333];
int seq[33333];
const int SEG_MAXN = 100000 + 5;
int seg[SEG_MAXN * 4], seg1[SEG_MAXN * 4];
int num[SEG_MAXN * 4];
inline void segpu(int x) {
  num[x] = num[x << 1] + num[x << 1 | 1];
  if (num[x << 1]) {
    seg[x] = (seg[x << 1] + 1ll * first[num[x << 1] - 1] * seg[x << 1 | 1] +
              1ll * first[num[x << 1]] * seg1[x << 1 | 1]) %
             mo;
    seg1[x] = (seg1[x << 1] + 1ll * first[num[x << 1]] * seg[x << 1 | 1] +
               1ll * first[num[x << 1] + 1] * seg1[x << 1 | 1]) %
              mo;
  } else {
    seg[x] = seg[x << 1 | 1];
    seg1[x] = seg1[x << 1 | 1];
  }
}
void seginit_in(int l, int r, int x) {
  if (l == r) {
    seg[x] = seg1[x] = 0;
    num[x] = 0;
  } else {
    int mid = l + r >> 1;
    seginit_in(l, mid, x << 1);
    seginit_in(mid + 1, r, x << 1 | 1);
    segpu(x);
  }
}
int l1, r1, I;
int sans;
bool ans_bo;
int stag;
void segupd_in(int l, int r, int x) {
  if (l == r) {
    seg[x] = 0, seg1[x] = stag * seq[l];
    num[x] = stag;
  } else {
    int mid = l + r >> 1;
    if (I <= mid)
      segupd_in(l, mid, x << 1);
    else
      segupd_in(mid + 1, r, x << 1 | 1);
    segpu(x);
  }
}
int segn;
void segupd(int i, int v) {
  stag = v, I = i;
  segupd_in(1, segn, 1);
}
void seginit(int n) {
  segn = n;
  seginit_in(1, segn, 1);
}
int n;
int ai[33333];
map<int, int> ma;
struct Q {
  int l, r, id;
} que[33333];
int q;
int tot = 0;
int SZ = 200;
int cmp(const Q& a, const Q& b) {
  if (a.l / SZ == b.l / SZ)
    return a.r < b.r;
  else
    return a.l < b.l;
}
int cl, cr;
int cnt[33333];
int out[33333];
void upd(int id, int del) {
  if (cnt[id] == 0 && del == 1) {
    segupd(id, 1);
  } else if (cnt[id] == 1 && del == -1) {
    segupd(id, 0);
  }
  cnt[id] += del;
}
void gaol(int l) {
  while (cl > l) {
    cl--;
    upd(ai[cl], 1);
  }
  while (cl < l) {
    upd(ai[cl], -1);
    cl++;
  }
}
void gaor(int r) {
  while (cr < r) {
    cr++;
    upd(ai[cr], 1);
  }
  while (cr > r) {
    upd(ai[cr], -1);
    cr--;
  }
}
int main() {
  gn(n);
  gn(mo);
  first[0] = 0;
  first[1] = 1 % mo;
  for (int i = (2), _ed = (30010); i < _ed; i++)
    first[i] = (first[i - 1] + first[i - 2]) % mo;
  for (int i = (1), _ed = (n + 1); i < _ed; i++) {
    gn(ai[i]);
    ma[ai[i]];
  }
  for (__typeof((ma).begin()) i = (ma).begin(); i != (ma).end(); i++)
    seq[i->second = ++tot] = (i->first) % mo;
  for (int i = (1), _ed = (n + 1); i < _ed; i++) ai[i] = ma[ai[i]];
  gn(q);
  for (int i = (1), _ed = (q + 1); i < _ed; i++)
    gn(que[i].l), gn(que[i].r), que[i].id = i;
  sort(que + 1, que + 1 + q, cmp);
  seginit(tot);
  cl = 1, cr = 0;
  for (int i = (1), _ed = (q + 1); i < _ed; i++) {
    if (cl > que[i].r)
      gaol(que[i].l), gaor(que[i].r);
    else
      gaor(que[i].r), gaol(que[i].l);
    out[que[i].id] = seg1[1];
  }
  for (int i = (1), _ed = (q + 1); i < _ed; i++) printf("%d\n", out[i]);
  return 0;
}
