#include <bits/stdc++.h>
using namespace std;
long long ql[300007], qr[300007], f[300007], pos[300007], ans[300007],
    mx[300007];
long long n, q, mod;
inline long long read() {
  long long res = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    res = res * 10 + ch - 48;
    ch = getchar();
  }
  return res * flag;
}
struct node {
  long long id, val;
} a[300007];
bool cmp(node x, node y) { return x.val < y.val; }
inline long long fastmod(long long x) { return x >= mod ? x - mod : x; }
signed main() {
  n = read(), mod = read();
  f[1] = f[2] = 1;
  for (long long i = 3; i <= n; ++i) {
    f[i] = fastmod(f[i - 1] + f[i - 2]);
  }
  for (long long i = 1; i <= n; ++i) {
    a[i].id = i;
    a[i].val = read();
  }
  sort(a + 1, a + 1 + n, cmp);
  q = read();
  for (long long i = 1; i <= q; ++i) {
    ql[i] = read(), qr[i] = read();
  }
  for (long long i = 1; i <= n; ++i) {
    long long res = a[i].val % mod;
    for (long long j = 1; j <= q; ++j) {
      if (a[i].id >= ql[j] && a[i].id <= qr[j] && a[i].val != mx[j]) {
        ans[j] += f[++pos[j]] * res;
        mx[j] = a[i].val;
      }
    }
  }
  for (long long i = 1; i <= q; ++i) {
    printf("%lld\n", ans[i] % mod);
  }
}
