#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
using namespace std::placeholders;
int max_fib = 2;
uint16_t fib_memo[30000];
uint16_t mod;
vector<int> range;
bool comp_idx(int i, int j) { return range[i] < range[j]; }
int max_bit(int a) {
  int count = 0;
  while (a & 1) {
    a >>= 1;
    count++;
  }
  return count;
}
void fill_fib(int n) {
  for (int i = max_fib; i < (n + 1); ++i) {
    fib_memo[i] = (uint16_t)(fib_memo[i - 2] + fib_memo[i - 1]);
    fib_memo[i] = fib_memo[i] % mod;
  }
  max_fib = max(max_fib, n + 1);
  return;
}
int main() {
  fib_memo[0] = 1;
  fib_memo[1] = 1;
  int amount;
  cin >> amount >> mod;
  fill_fib(29999);
  range.reserve(amount);
  vector<int> idx;
  idx.reserve(amount);
  for (int i = 0; i < (amount); ++i) {
    int a;
    cin >> a;
    idx.push_back(i);
    range.push_back(a);
  }
  sort(idx.begin(), idx.end(), comp_idx);
  vector<int> range_unmodded;
  vector<uint16_t> range_modded;
  range_modded.reserve(amount);
  range_unmodded.reserve(amount);
  for (int i = 0; i < (amount); ++i) {
    range_unmodded.push_back(range[idx[i]]);
    range_modded.push_back((uint16_t)(range[idx[i]] % (uint32_t)mod));
  }
  int queries;
  cin >> queries;
  for (int i = 0; i < (queries); ++i) {
    int start, end;
    cin >> start >> end;
    start--;
    end--;
    int last_item = -1;
    int fib_counter = 0;
    uint64_t sum = 0;
    for (int j = 0; j < (amount); ++j) {
      if (((uint32_t)idx[j] - start <= (uint32_t)(end - start)) &&
          (last_item != range_unmodded[j])) {
        last_item = range_unmodded[j];
        uint32_t product = range_modded[j] * fib_memo[fib_counter++];
        sum += product;
      }
    }
    cout << sum % mod << '\n';
  }
}
