#include <bits/stdc++.h>
using namespace std;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "Yes" : "No");
  exit(0);
}
void addmod(int &x, int y, int mod) {
  x += y;
  if (x >= mod) x -= mod;
}
int fib[30005], l[30005], r[30005], la[30005], cnt[30005], ans[30005];
pair<int, int> a[30005];
void fmain() {
  scanf("%d%d", &n, &m);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a + 1, a + 1 + n);
  fib[1] = 1;
  for (int i = 2; i <= n; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % m;
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", l + i, r + i);
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    for (int(j) = 1; (j) <= (int)(q); (j)++) {
      if (a[i].second < l[j] || a[i].second > r[j] || a[i].first == la[j])
        continue;
      la[j] = a[i].first;
      addmod(ans[j], la[j] % m * fib[++cnt[j]] % m, m);
    }
  }
  for (int(j) = 1; (j) <= (int)(q); (j)++) printf("%d\n", ans[j]);
}
int main() {
  fmain();
  return 0;
}
