#include <bits/stdc++.h>
using namespace std;
inline char nchar() {
  static const int bufl = 1 << 20;
  static char buf[bufl], *a, *b;
  return a == b && (b = (a = buf) + fread(buf, 1, bufl, stdin), a == b) ? EOF
                                                                        : *a++;
}
inline int read() {
  int x = 0, f = 1;
  char c = nchar();
  for (; !isdigit(c); c = nchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = nchar()) x = x * 10 + c - '0';
  return x * f;
}
inline void write(int x) {
  if (!x)
    puts("0");
  else {
    static char s[12];
    int tot = 0;
    for (; x; x /= 10) s[++tot] = x % 10 + '0';
    while (tot) putchar(s[tot--]);
    puts("");
  }
}
const int maxn = 3e4 + 1;
int n, m, q, block[maxn], size, a[maxn], dc[maxn], u, dq[maxn];
int fib[maxn], ans[maxn];
inline int Plus(int x, int y) { return (x + y) % q; }
inline int Multi(int x, int y) { return x * y % q; }
inline int Sub(int x, int y) { return Plus(x, q - y); }
struct query {
  int l, r, id;
  inline bool operator<(const query& b) const {
    return block[l] != block[b.l] ? block[l] < block[b.l] : r < b.r;
  }
} b[maxn];
struct Mat {
  int a[2][2];
  Mat() { memset(a, 0, sizeof a); }
  Mat(int b, int c, int d, int e) {
    a[0][0] = b, a[0][1] = c, a[1][0] = d, a[1][1] = e;
  }
  inline int* operator[](int x) { return a[x]; }
  inline void eye() { a[0][0] = a[1][1] = 1; }
} nxt[maxn];
inline Mat operator*(Mat a, Mat b) {
  Mat ret;
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k)
        ret.a[i][j] = Plus(ret.a[i][j], Multi(a.a[i][k], b.a[k][j]));
  return ret;
}
struct lie {
  int a[2];
  lie(int x = 0, int y = 0) { a[0] = x, a[1] = y; }
  inline int& operator[](int x) { return a[x]; }
};
inline lie operator*(Mat a, lie b) {
  int c[2] = {0, 0};
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j) c[i] = Plus(c[i], Multi(a[i][j], b[j]));
  return lie(c[0], c[1]);
}
inline lie operator+(lie a, lie b) {
  return lie(Plus(a.a[0], b.a[0]), Plus(a.a[1], b.a[1]));
}
namespace sgt {
lie t[maxn << 1];
int how[maxn << 1], what[maxn << 1];
inline int ID(int l, int r) { return l + r | l != r; }
void mpoint(int l, int r, int p, int d) {
  int x = ID(l, r);
  if (l == r) {
    what[x] = (bool)(how[x] += d);
    if (!how[x])
      t[x] = (lie){0, 0};
    else if (how[x] == 1 && d == 1)
      t[x] = (lie){dq[l], 0};
    return;
  }
  int mid = (l + r) >> 1, lc = ID(l, mid), rc = ID(mid + 1, r);
  p <= mid ? mpoint(l, mid, p, d) : mpoint(mid + 1, r, p, d);
  int ls = what[lc];
  what[x] = what[lc] + what[rc];
  t[x] = t[lc] + nxt[ls] * t[rc];
}
inline int getans() { return t[ID(1, u)][0]; }
void mpoint(int x, int d) { mpoint(1, u, x, d); }
}  // namespace sgt
inline void inc(int p) {
  int x = a[p];
  sgt::mpoint(x, 1);
}
inline void dec(int p) {
  int x = a[p];
  sgt::mpoint(x, -1);
}
int main() {
  size = max(1, (int)sqrt(n = read())), q = read();
  nxt[0].eye(), nxt[1] = Mat(1, 1, 1, 0);
  for (int i = 2; i <= n; ++i) nxt[i] = nxt[i - 1] * nxt[1];
  fib[1] = fib[2] = 1;
  for (int i = 3; i <= n; ++i) fib[i] = Plus(fib[i - 1], fib[i - 2]);
  for (int i = 1; i <= n; ++i) block[i] = (i - 1) / size + 1;
  for (int i = 1; i <= n; ++i) a[i] = dc[i] = read();
  sort(dc + 1, dc + n + 1), u = unique(dc + 1, dc + n + 1) - dc - 1;
  for (int i = 1; i <= n; ++i) dq[i] = dc[i] % q;
  for (int i = 1; i <= n; ++i)
    a[i] = lower_bound(dc + 1, dc + u + 1, a[i]) - dc;
  m = read();
  for (int i = 1; i <= m; ++i) {
    int l = read(), r = read();
    b[i] = (query){l, r, i};
  }
  sort(b + 1, b + m + 1);
  int l = 1, r = 0;
  for (int i = 1; i <= m; ++i) {
    int &ql = b[i].l, &qr = b[i].r, &id = b[i].id;
    while (r < qr) inc(++r);
    while (l > ql) inc(--l);
    while (r > qr) dec(r--);
    while (l < ql) dec(l++);
    ans[id] = sgt::getans();
  }
  for_each(ans + 1, ans + m + 1, write);
  return 0;
}
