#include <bits/stdc++.h>
using namespace std;
const int maxN = 3e4 + 5;
pair<int, int> a[maxN];
int am[maxN], f[maxN];
int Re() {
  int ch = '@', x = 0;
  for (; ch < 48 || 57 < ch; ch = getchar())
    ;
  for (; 47 < ch && ch < 58; ch = getchar()) x = x * 10 + ch - 48;
  return x;
}
int main() {
  int n = Re(), m = Re();
  for (int i = 1; i <= n; ++i) {
    a[i].first = Re();
    a[i].second = i;
  }
  sort(a + 1, a + 1 + n);
  f[0] = 0;
  f[1] = 1;
  am[1] = a[1].first % m;
  for (int i = 2; i <= n; ++i) {
    f[i] = f[i - 1] + f[i - 2];
    if (f[i] >= m) f[i] -= m;
    am[i] = a[i].first % m;
  }
  int q;
  scanf("%d", &q);
  for (int i = 1, l, r, last, step, ans; i <= q; ++i) {
    l = Re();
    r = Re();
    last = -1;
    step = 0;
    ans = 0;
    for (int j = 1; j <= n; ++j)
      if (l <= a[j].second && a[j].second <= r && a[j].first != last) {
        ans = (ans + am[j] * f[++step]) % m;
        last = a[j].first;
      }
    printf("%d\n", ans);
  }
  return 0;
}
