#include <bits/stdc++.h>
using namespace std;
inline void EnableFileIO(const string &fileName) {
  if (fileName.empty()) return;
  freopen((fileName + ".in").c_str(), "r", stdin);
  freopen((fileName + ".out").c_str(), "w", stdout);
  return;
}
const int INF = (1 << 30) - 1;
const long long LINF = (1LL << 61) - 1;
const double EPS = 1e-10, PI = acos(-1);
const int N = 3e4 + 100, MAGIC = 200;
int n, P, m;
pair<int, int> a[N], q[N];
int cnt[N], maxi[N];
long long f[N], ans[N];
int main() {
  srand((int)time(0));
  EnableFileIO("");
  scanf("%d%d", &n, &P);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a, a + n);
  f[0] = 1, f[1] = 1;
  for (int i = 2; i <= n; i++) f[i] = (f[i - 1] + f[i - 2]) % P;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &q[i].first, &q[i].second);
    --q[i].first, --q[i].second;
  }
  memset(maxi, -1, sizeof maxi);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      if (q[j].first <= a[i].second && a[i].second <= q[j].second &&
          a[i].first > maxi[j]) {
        ans[j] += a[i].first * f[cnt[j]++];
        maxi[j] = a[i].first;
      }
    }
  }
  for (int i = 0; i < m; i++) {
    printf("%lld\n", ans[i] % P);
  }
  return 0;
}
