#include <bits/stdc++.h>
using namespace std;
int n, m;
int first[33333];
pair<int, int> a[33333];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a, a + n);
  first[0] = first[1] = 1 % m;
  for (int i = 2; i <= n; i++) {
    first[i] = first[i - 1] + first[i - 2];
    if (first[i] >= m) {
      first[i] -= m;
    }
  }
  int l, r, q;
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &l, &r);
    --l, --r;
    long long sum = 0, color = -1, i = 0;
    for (int j = 0; j < n; j++) {
      if (color == a[j].first) continue;
      if (l <= a[j].second && a[j].second <= r) {
        color = a[j].first;
        sum += 1ll * first[i++] * a[j].first;
      }
    }
    printf("%d\n", int(sum % m));
  }
  return 0;
}
