#include <bits/stdc++.h>
using namespace std;
int F[30030];
int n;
int mod;
int a[30030], id[30030];
int nxt[30030];
bool cmp(int i, int j) { return a[i] < a[j]; }
int m;
struct pnt {
  int l, r, i;
  pnt(int l = 0, int r = 0, int i = 0) : l(l), r(r), i(i){};
} q[30030];
bool operator<(pnt a, pnt b) { return b.l != a.l ? a.l < b.l : a.r < b.r; }
int answer[30030];
int calc(int l, int r) {
  int s = 0, m = 0;
  for (int j, i = 1; i <= n; i++) {
    j = id[i];
    if (j >= l && j <= r) {
      s = (s + F[++m] * a[j]) % mod;
      i = nxt[i];
    }
  }
  return s;
}
int main() {
  scanf("%d %d", &n, &mod);
  F[1] = F[2] = 1 % mod;
  for (int i = 3; i <= n; i++) {
    F[i] = (F[i - 1] + F[i - 2]) % mod;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    id[i] = i;
  }
  sort(id + 1, id + n + 1, cmp);
  nxt[n] = n;
  for (int j = n - 1; j >= 1; j--) {
    if (a[id[j]] == a[id[j + 1]]) {
      nxt[j] = nxt[j + 1];
    } else {
      nxt[j] = j;
    }
  }
  for (int j = 1; j <= n; j++) {
    a[j] %= mod;
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &q[i].l, &q[i].r);
    q[i].i = i;
  }
  sort(q + 1, q + m + 1);
  for (int i = 1; i <= m; i++) {
    if (i > 1 && q[i].l == q[i - 1].l && q[i].r == q[i - 1].r) {
      answer[q[i].i] = answer[q[i - 1].i];
    } else {
      answer[q[i].i] = calc(q[i].l, q[i].r);
    }
  }
  for (int i = 1; i <= m; i++) {
    printf("%d\n", answer[i]);
  }
  return 0;
}
