#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int T = 30033;
int N, q, mod;
vector<bitset<T> > v(2 * T);
bitset<T> get(int l, int r) {
  bitset<T> ret;
  for (l += N, r += N; l < r; l /= 2, r /= 2) {
    if (l & 1) ret |= v[l++];
    if (r & 1) ret |= v[--r];
  }
  return ret;
}
int num[T], fib[T];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  scanf("%d%d", &N, &mod);
  map<int, vector<int> > mp;
  for (int i = (0); i < (N); i++) {
    int k;
    scanf("%d", &k);
    mp[k].push_back(i);
  }
  int a = 0, mx = mp.size();
  for (auto it = mp.begin(); it != mp.end(); it++) {
    for (int i : it->second) v[N + i][a] = 1;
    num[a++] = (it->first) % mod;
  }
  for (int i = N; i-- > 0;) v[i] = v[2 * i] | v[(2 * i) ^ 1];
  fib[0] = fib[1] = 1;
  for (int i = (2); i < (T); i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  scanf("%d", &q);
  vector<pair<int, int> > que(q);
  vector<int> Ans(q);
  for (int i = (0); i < (q); i++) {
    scanf("%d%d", &(que[i].first), &(que[i].second));
    que[i].first--;
  }
  for (int i = (0); i < (q); i++) {
    bitset<T> b = get(que[i].first, que[i].second);
    int c = 0;
    uint64_t ans = 0;
    for (int j = 0; j < mx;) {
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
      ans += b[j] * fib[c] * num[j];
      c += b[j++];
    }
    Ans[i] = ans % mod;
  }
  for (int i = (0); i < (q); i++) printf("%d\n", Ans[i]);
}
