#include <bits/stdc++.h>
using namespace std;
int i, j, n, m, k;
int a[200000], u[200000], c[200000], h[200000], val[200000];
int f[100000];
map<int, int> mp;
int main() {
  cin >> n >> m;
  f[0] = f[1] = 1;
  f[0] %= m;
  f[1] %= m;
  for (i = 2; i < 100000; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % m;
  }
  for (i = 0; i < n; i++) {
    cin >> a[i];
    c[i] = a[i];
  }
  int nom = 1;
  sort(c, c + n);
  mp[c[0]] = 0;
  val[0] = c[0] % m;
  for (i = 1; i < n; i++) {
    if (c[i] != c[i - 1]) {
      val[nom] = c[i] % m;
      mp[c[i]] = nom++;
    }
  }
  for (i = 0; i < n; i++) {
    h[i] = mp[a[i]];
  }
  int q;
  cin >> q;
  for (i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    l--, r--;
    for (j = l; j <= r; j++) {
      u[h[j]] = 1;
    }
    long long ans = 0;
    int cur = 0;
    for (j = 0; j < nom; j++) {
      if (u[j]) {
        ans += val[j] * f[cur++];
        u[j] = 0;
      }
    }
    ans %= m;
    printf("%d\n", ans);
  }
  return 0;
}
