#include <bits/stdc++.h>
using namespace std;
long long int powm(long long int a, int b, int n) {
  long long int rm = 1;
  while (b) {
    if (b % 2) {
      rm = (rm * a) % n;
    }
    a = (a * a) % n;
    b /= 2;
  }
  return rm;
}
int a[int(30000 + 1000)], b[int(30000 + 1000)], t = 0;
map<int, int> Hash;
int wall[int(30000 + 1000)] = {0};
vector<int> vec[int(30000 + 1000)];
int fib[int(30000 + 1000)], ans[int(30000 + 1000)] = {0}, l[int(30000 + 1000)],
                                            r[int(30000 + 1000)];
int main() {
  int n, m, Q;
  scanf("%d", &n);
  ;
  scanf("%d", &m);
  ;
  for (int i = int(1); i <= (int)n; i++) {
    scanf("%d", &a[i]);
    ;
    b[i] = a[i];
  }
  scanf("%d", &Q);
  ;
  for (int i = int(1); i <= (int)Q; i++) {
    scanf("%d", &l[i]);
    ;
    scanf("%d", &r[i]);
    ;
    vec[r[i]].push_back(i);
  }
  fib[1] = fib[2] = 1;
  for (int i = 3; i <= n; ++i) fib[i] = (fib[i - 1] + fib[i - 2]) % m;
  sort(b + 1, b + n + 1);
  t = 1;
  for (int i = 2; i <= n; ++i)
    if (b[i] != b[i - 1]) b[++t] = b[i];
  for (int i = int(1); i <= (int)t; i++) Hash[b[i]] = i;
  for (int i = int(1); i <= (int)n; i++) a[i] = Hash[a[i]];
  for (int i = int(1); i <= (int)t; i++) b[i] %= m;
  int qid, cnt, idx, A, szz;
  for (int i = 1; i <= n; ++i) {
    wall[a[i]] = i;
    szz = vec[i].size();
    for (int j = 0; j < szz; ++j) {
      cnt = 0;
      qid = vec[i][j];
      A = 0;
      for (int k = 1; k <= t; ++k) {
        if (wall[k] >= l[qid]) {
          cnt++;
          A = (A + fib[cnt] * b[k]) % m;
        }
      }
      ans[qid] = A;
    }
  }
  for (int i = int(1); i <= (int)Q; i++) cout << ans[i] << endl;
  return 0;
}
