#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
const int N = 30005;
int n, m, Qi, f[N], l[N], r[N], h[N], ans[N], las[N];
std::pair<int, int> a[N];
int main() {
  memset(las, -1, sizeof las);
  scanf("%d%d", &n, &m);
  f[1] = f[2] = 1;
  for (int i = 3; i <= n; ++i) {
    f[i] = (f[i - 2] + f[i - 1]) % m;
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  std::sort(a + 1, a + 1 + n);
  scanf("%d", &Qi);
  for (int i = 1; i <= Qi; ++i) {
    scanf("%d%d", &l[i], &r[i]);
  }
  for (int i = 1; i <= n; ++i) {
    int t = a[i].first % m;
    for (int j = 1; j <= Qi; ++j) {
      if (l[j] <= a[i].second && a[i].second <= r[j] && a[i].first != las[j]) {
        las[j] = a[i].first;
        ++h[j];
        ans[j] = (ans[j] + f[h[j]] * t) % m;
      }
    }
  }
  for (int i = 1; i <= Qi; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
