#include <bits/stdc++.h>
using namespace std;
struct ai {
  int a, num;
  bool operator<(const ai &B) const { return a < B.a; }
} a[30001];
int n, m, q, top;
int num[30001], l[30001], r[30001], la[30001];
int fi[30001];
int ans[30001];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i].a);
    a[i].num = i;
  }
  sort(a + 1, a + 1 + n);
  fi[1] = 1;
  for (int i = 2; i <= n; i++) fi[i] = (fi[i - 1] + fi[i - 2]) % m;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &l[i], &r[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < q; j++) {
      if (a[i].num < l[j] || a[i].num > r[j] || a[i].a == la[j]) continue;
      ans[j] = (ans[j] + ((la[j] = a[i].a) % m) * (fi[++num[j]])) % m;
    }
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
  return 0;
}
