#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("-Ofast", "-funroll-all-loops", "-ffast-math")
#pragma GCC target("avx2,fma")
#pragma GCC optimize("unroll-loops")
using namespace std;
const long long Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 2e5;
char buf[100000], *p1 = buf, *p2 = buf;
inline char nc() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  int w = 1, data = 0;
  char ch = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = nc();
  if (ch == '-') w = -1, ch = nc();
  while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = nc();
  return w * data;
}
int blLen, P, bas = 1e5;
struct Que {
  int l, r, id;
  bool operator<(const Que& oth) const {
    return ((l / blLen) ^ (oth.l / blLen)) ? l / blLen < oth.l / blLen
           : ((l / blLen) & 1)             ? r < oth.r
                                           : r > oth.r;
  }
} que[MAXN];
int n, q, a[MAXN], b[MAXN], coN, fib[MAXN];
struct Node {
  int lVal, Val, addv;
};
struct Segment_Tree {
  Node v[MAXN << 2];
  void PushUp(int rt) {
    v[rt].lVal = (v[rt << 1].lVal + v[rt << 1 | 1].lVal) % P;
    v[rt].Val = (v[rt << 1].Val + v[rt << 1 | 1].Val) % P;
  }
  void Add(int l, int r, int C, int rt) {
    long long lVal = ((1ll * v[rt].lVal * fib[bas + C - 1]) +
                      (1ll * v[rt].Val * fib[bas + C])) %
                     P;
    long long Val = ((1ll * v[rt].lVal * fib[bas + C]) +
                     (1ll * v[rt].Val * fib[bas + C + 1])) %
                    P;
    v[rt].lVal = lVal;
    v[rt].Val = Val;
    v[rt].addv += C;
  }
  void PushDown(int l, int r, int rt) {
    if (v[rt].addv) {
      int mid = (l + r) >> 1;
      Add(l, mid, v[rt].addv, rt << 1);
      Add(mid + 1, r, v[rt].addv, rt << 1 | 1);
      v[rt].addv = 0;
    }
  }
  void UpdateAdd(int L, int C, int l, int r, int rt) {
    if (l == r) {
      v[rt].lVal = 1ll * b[l] % P * fib[bas + v[rt].addv] % P;
      v[rt].Val = 1ll * b[l] % P * fib[bas + v[rt].addv + 1] % P;
      return;
    }
    int mid = (l + r) >> 1;
    PushDown(l, r, rt);
    if (L <= mid)
      UpdateAdd(L, C, l, mid, rt << 1), Add(mid + 1, r, C, rt << 1 | 1);
    else
      UpdateAdd(L, C, mid + 1, r, rt << 1 | 1);
    PushUp(rt);
  }
  void UpdateRemove(int L, int C, int l, int r, int rt) {
    if (l == r) {
      v[rt].lVal = v[rt].Val = 0;
      return;
    }
    int mid = (l + r) >> 1;
    PushDown(l, r, rt);
    if (L <= mid)
      UpdateRemove(L, C, l, mid, rt << 1), Add(mid + 1, r, C, rt << 1 | 1);
    else
      UpdateRemove(L, C, mid + 1, r, rt << 1 | 1);
    PushUp(rt);
  }
} t;
int cnt[MAXN];
void add(int x) {
  if (!cnt[x]) t.UpdateAdd(x, 1, 1, coN, 1);
  cnt[x]++;
}
void remove(int x) {
  --cnt[x];
  if (!cnt[x]) t.UpdateRemove(x, -1, 1, coN, 1);
}
int ans[MAXN];
int32_t main() {
  n = read();
  P = read();
  blLen = sqrt(n);
  for (int i = 1; i <= n; i++) b[i] = a[i] = read();
  q = read();
  for (int i = 1; i <= q; i++) que[que[i].id = i].l = read(), que[i].r = read();
  sort(que + 1, que + q + 1);
  sort(b + 1, b + n + 1);
  coN = unique(b + 1, b + n + 1) - b - 1;
  for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + coN + 1, a[i]) - b;
  fib[bas] = 0;
  fib[bas + 1] = 1;
  for (int i = 2; bas + i < MAXN; i++)
    fib[bas + i] = (1ll * fib[bas + i - 1] + fib[bas + i - 2]) % P;
  for (int i = 1; bas - i >= 0; i++)
    fib[bas - i] = (1ll * fib[bas - i + 2] - fib[bas - i + 1] + P) % P;
  int l = 1, r = 0;
  for (int i = 1; i <= q; i++) {
    while (l < que[i].l) remove(a[l++]);
    while (l > que[i].l) add(a[--l]);
    while (r < que[i].r) add(a[++r]);
    while (r > que[i].r) remove(a[r--]);
    ans[que[i].id] = t.v[1].Val;
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}
