#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
using namespace std;
bool Finish_read;
template <class T>
inline void read(T &x) {
  Finish_read = 0;
  x = 0;
  int f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    if (ch == EOF) return;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  x *= f;
  Finish_read = 1;
}
template <class T>
inline void print(T x) {
  if (x / 10 != 0) print(x / 10);
  putchar(x % 10 + '0');
}
template <class T>
inline void writeln(T x) {
  if (x < 0) putchar('-');
  x = abs(x);
  print(x);
  putchar('\n');
}
template <class T>
inline void write(T x) {
  if (x < 0) putchar('-');
  x = abs(x);
  print(x);
}
const int maxn = 30005;
struct node {
  int x, id;
  inline bool operator<(const node &rhs) const {
    return x == rhs.x ? id < rhs.id : x < rhs.x;
  }
} a[maxn];
int n, mod, f[maxn], lst[maxn], q, l[maxn], r[maxn], ans[maxn], cnt[maxn];
int main() {
  memset(lst, -1, sizeof lst);
  read(n), read(mod);
  f[1] = f[2] = 1;
  for (register int i = 3; i <= n; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  for (register int i = 1; i <= n; ++i) read(a[i].x), a[i].id = i;
  sort(a + 1, a + n + 1);
  read(q);
  for (register int i = 1; i <= q; ++i) read(l[i]), read(r[i]);
  for (register int i = 1; i <= n; ++i) {
    register int tmp = a[i].x % mod;
    for (register int j = 1; j <= q; ++j)
      if (l[j] <= a[i].id && a[i].id <= r[j] && a[i].x != lst[j]) {
        lst[j] = a[i].x, ans[j] += f[++cnt[j]] * tmp % mod;
        if (ans[j] >= mod) ans[j] -= mod;
      }
  }
  for (register int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}
