#include <bits/stdc++.h>
using namespace std;
int main() {
  srand(time(NULL));
  int length(30000), modolu(rand() % 30000);
  cin >> length >> modolu;
  int fibonacci[30000];
  fibonacci[0] = fibonacci[1] = 1;
  for (int i = 2; i < 30000; ++i)
    fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % modolu;
  vector<pair<int, int> > values(length);
  for (int i = 0; i < length; ++i) {
    cin >> values[i].first;
    values[i].second = i + 1;
  }
  sort(values.begin(), values.end());
  vector<int> jump(length, length);
  for (int i = 1; i < length; ++i) {
    if (values[i].first != values[i - 1].first) {
      for (int j = 1; j <= i && values[i - j].first == values[i - 1].first;
           ++j) {
        jump[i - j] = j - 1;
      }
    }
  }
  for (int i = 0; i < length; ++i) values[i].first = values[i].first % modolu;
  int queries(30000);
  cin >> queries;
  for (int q = 0; q < queries; ++q) {
    unsigned long long int answer = 0;
    int count = 0;
    int l, r;
    cin >> l >> r;
    for (int i = 0; i < values.size(); ++i) {
      if (values[i].second >= l & values[i].second <= r) {
        answer += values[i].first * fibonacci[count];
        i += jump[i];
        ++count;
      }
    }
    cout << answer % modolu << '\n';
  }
  return 0;
}
