#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int MD = 1000000007;
int n, m, q, cnt[N];
int fi[N], a[N];
int l[N], r[N], lst[N];
long long val[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  fi[1] = fi[2] = 1 % m;
  for (int i = 3; i < N; ++i) fi[i] = (fi[i - 1] + fi[i - 2]) % m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  cin >> q;
  vector<pair<int, int> > v;
  for (int i = 1; i <= n; ++i) v.push_back(make_pair(a[i], i));
  sort(v.begin(), v.end());
  for (int _tmp = q, i = 1; i <= _tmp; ++i) cin >> l[i] >> r[i];
  for (int i = 0; i < v.size(); ++i) {
    int x = v[i].first, y = v[i].second;
    for (int _tmp = q, j = 1; j <= _tmp; ++j)
      if (l[j] <= y && y <= r[j] && lst[j] < x) {
        lst[j] = x;
        cnt[j]++;
        val[j] += 1LL * fi[cnt[j]] * x;
      }
  }
  for (int _tmp = q, i = 1; i <= _tmp; ++i) cout << val[i] % m << '\n';
  return 0;
}
