#include <bits/stdc++.h>
using namespace std;
const int iinf = 1e9 + 7;
const long long linf = 1ll << 60;
const double dinf = 1e60;
template <typename T>
inline void scf(T &x) {
  bool f = 0;
  x = 0;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-') c = getchar();
  if (c == '-') {
    f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  if (f) x = -x;
  return;
}
template <typename T1, typename T2>
void scf(T1 &x, T2 &y) {
  scf(x);
  return scf(y);
}
template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) {
  scf(x);
  scf(y);
  return scf(z);
}
template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
  scf(x);
  scf(y);
  scf(z);
  return scf(w);
}
inline char mygetchar() {
  char c = getchar();
  while (c == ' ' || c == '\n') c = getchar();
  return c;
}
template <typename T>
void chkmax(T &x, const T &y) {
  if (y > x) x = y;
  return;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
  return;
}
const int N = 3e4 + 100;
int n, mod, q_n;
int fib[N];
pair<int, int> a[N];
int l[N], r[N], lst[N];
int cnt[N];
long long ans[N];
void TZL() {
  scf(n, mod);
  for (int i = (1); i <= (n); ++i) scf(a[i].first), a[i].second = i;
  sort(a + 1, a + n + 1);
  scf(q_n);
  for (int i = (1); i <= (q_n); ++i) scf(l[i], r[i]), lst[i] = -1;
  fib[0] = 0;
  fib[1] = fib[2] = 1;
  for (int i = (3); i <= (n); ++i) {
    fib[i] = fib[i - 1] + fib[i - 2];
    if (fib[i] >= mod) fib[i] -= mod;
  }
  return;
}
void RANK1() {
  auto t = a;
  int x, i;
  for (int _ = (1); _ <= (n); ++_) {
    t++;
    x = t->first, i = t->second;
    for (int j = (1); j <= (q_n); ++j)
      if (l[j] <= i && i <= r[j] && x != lst[j])
        ans[j] += 1ll * x * fib[(++cnt[j])], lst[j] = x;
  }
  for (int i = (1); i <= (q_n); ++i) printf("%d\n", (int)(ans[i] % mod));
  return;
}
int main() {
  TZL();
  RANK1();
  return 0;
}
