#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30000 + 10;
const int INF = ~0U >> 1;
pair<int, int> a[MAX_N];
int n, m, fib[MAX_N], b[MAX_N];
int main() {
  scanf("%d%d", &n, &m);
  fib[1] = fib[2] = 1 % m;
  for (int i = 3; i < MAX_N; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % m;
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    a[i] = make_pair(x, i);
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) b[i] = a[i].first % m;
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    long long ans = 0;
    int pre = -INF, cur = 1;
    for (int i = 1; i <= n; i++)
      if (l <= a[i].second && a[i].second <= r && a[i].first > pre) {
        ans += 1LL * b[i] * fib[cur++];
        pre = a[i].first;
      }
    printf("%I64d\n", ans % m);
  }
  return 0;
}
