#include <bits/stdc++.h>
using namespace std;
const int maxn = 30010;
pair<int, int> a[maxn];
int f[maxn], L[maxn], R[maxn], num[maxn], ans[maxn], lt[maxn];
int main() {
  int N, M, P;
  scanf("%d%d", &N, &P);
  f[1] = 1;
  f[2] = 1;
  for (int i = 3; i <= N; i++) f[i] = (f[i - 1] + f[i - 2]) % P;
  for (int i = 1; i <= N; i++)
    scanf("%d", &a[i].first), a[i].first, a[i].second = i;
  sort(a + 1, a + N + 1);
  scanf("%d", &M);
  for (int i = 1; i <= M; i++) {
    scanf("%d%d", &L[i], &R[i]);
    lt[i] = -1;
  }
  for (int i = 1; i <= N; i++) {
    int d = a[i].first % P;
    for (int j = 1; j <= M; j++) {
      if (a[i].second > R[j] || a[i].second < L[j]) continue;
      if (a[i].first == lt[j]) continue;
      ans[j] = (ans[j] + f[++num[j]] * d) % P;
      lt[j] = a[i].first;
    }
  }
  for (int i = 1; i <= M; i++) printf("%d\n", ans[i]);
  return 0;
}
