#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int neg = 1, num = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') neg = -1;
  for (; isdigit(c); c = getchar()) num = (num << 1) + (num << 3) + c - '0';
  return neg * num;
}
struct node {
  int id, val;
} a[30100];
int n, m, l[30100], r[30100], Max[30100], f[30100], now[30100];
long long ans[30100];
inline bool cmp(node x, node y) { return x.val < y.val; }
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) a[i].val = read(), a[i].id = i;
  sort(a + 1, a + n + 1, cmp);
  f[1] = f[2] = 1;
  for (int i = 3; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % m;
  int q = read();
  for (int i = 1; i <= q; i++) {
    l[i] = read();
    r[i] = read();
    Max[i] = -1;
  }
  for (int i = 1; i <= n; i++) {
    int x = a[i].val % m;
    for (int j = 1; j <= q; j++) {
      if (a[i].id >= l[j] && a[i].id <= r[j] && a[i].val != Max[j]) {
        Max[j] = a[i].val;
        ans[j] += f[++now[j]] * x;
      }
    }
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i] % m);
  return 0;
}
