#include <bits/stdc++.h>
using namespace std;
const int SZ = 3e4 + 8;
int M;
int fibs[SZ], vals[SZ], ar[SZ];
int st[4 * SZ][2], lazy[4 * SZ];
void preprocess() {
  fibs[0] = 0;
  fibs[1] = 1;
  for (int i = 2; i < SZ; i++) fibs[i] = (fibs[i - 1] + fibs[i - 2]) % M;
  for (int i = 2; i < SZ; i += 2) fibs[i] = -fibs[i];
}
inline int modulo(int x, int m) {
  x %= m;
  if (x < 0) x += m;
  return x;
}
void update(int s, int e, int x, int i, int n, bool toadd) {
  if (lazy[i] != 0) {
    int a, b, c, d;
    if (lazy[i] > 0) {
      a = abs(fibs[lazy[i] + 1]);
      b = c = abs(fibs[lazy[i]]);
      d = abs(fibs[lazy[i] - 1]);
    } else if (lazy[i] < 0) {
      a = fibs[-(lazy[i] + 1)];
      b = c = fibs[-lazy[i]];
      d = fibs[-(lazy[i] - 1)];
    }
    a = a * st[i][0];
    b = b * st[i][1];
    c = c * st[i][0];
    d = d * st[i][1];
    st[i][0] = modulo(a + b, M);
    st[i][1] = modulo(c + d, M);
    if (s != e) lazy[2 * i + 1] += lazy[i], lazy[2 * i + 2] += lazy[i];
    lazy[i] = 0;
  }
  if (x > e) return;
  if (x < s) {
    int a = st[i][0];
    int b = st[i][1];
    if (toadd) {
      st[i][0] = modulo(a + b, M);
      st[i][1] = a;
      if (s != e) lazy[2 * i + 1]++, lazy[2 * i + 2]++;
    } else {
      st[i][0] = b;
      st[i][1] = modulo(a - b, M);
      if (s != e) lazy[2 * i + 1]--, lazy[2 * i + 2]--;
    }
    return;
  }
  if (s == e) {
    if (toadd) {
      int xr = vals[s];
      st[i][0] = (xr * abs(fibs[n])) % M;
      st[i][1] = (xr * abs(fibs[n - 1])) % M;
    } else
      st[i][0] = st[i][1] = 0;
    return;
  }
  int mid = (s + e) / 2;
  update(s, mid, x, 2 * i + 1, n, toadd);
  update(mid + 1, e, x, 2 * i + 2, n, toadd);
  int a = st[2 * i + 1][0], b = st[2 * i + 1][1];
  int c = st[2 * i + 2][0], d = st[2 * i + 2][1];
  st[i][0] = (a + c) % M;
  st[i][1] = (b + d) % M;
}
int sqn;
inline bool sub(pair<int, int> x, pair<int, int> y) {
  double v1 = x.first;
  v1 = ceil(v1 / sqn);
  double v2 = y.first;
  v2 = ceil(v2 / sqn);
  if (v1 == v2)
    return x.second < y.second;
  else
    return v1 < v2;
}
int bit[SZ];
int l = SZ;
void bit_update(int i, int val) {
  while (i <= l) {
    bit[i] = bit[i] + val;
    i = i + (i & (-i));
  }
}
int bit_summ(int a) {
  int s = 0;
  while (a > 0) {
    s += bit[a];
    a = a - (a & (-a));
  }
  return s;
}
bool compare(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2) {
  int b = sqn;
  pair<int, int> x, y;
  x = p1.first;
  y = p2.first;
  if ((x.first / b) != (y.first / b)) return (x.first / b < y.first / b);
  return (x.second < y.second);
}
int ans[SZ], num[SZ];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, Q, l, r;
  cin >> N >> M;
  preprocess();
  sqn = sqrt(N);
  for (int i = 1; i <= N; i++) {
    cin >> ar[i];
    vals[i - 1] = ar[i];
  }
  sort(vals, vals + N);
  for (int i = 1; i <= N; i++)
    ar[i] = lower_bound(vals, vals + N, ar[i]) - vals;
  for (int i = 0; i < N; i++) vals[i] %= M;
  cin >> Q;
  vector<pair<pair<int, int>, int> > queries;
  for (int i = 0; i < Q; i++) {
    cin >> l >> r;
    queries.push_back(make_pair(make_pair(l, r), i));
  }
  sort(queries.begin(), queries.end(), compare);
  l = r = 1;
  num[ar[1]]++;
  bit_update(ar[1] + 1, 1);
  update(0, N - 1, ar[1], 0, 1, true);
  for (int i = 0; i < queries.size(); i++) {
    pair<int, int> p = queries[i].first;
    int ix = queries[i].second, pos;
    while (l < p.first) {
      num[ar[l]]--;
      if (num[ar[l]] == 0) {
        bit_update(ar[l] + 1, -1);
        update(0, N - 1, ar[l], 0, 0, false);
      }
      l++;
    }
    while (l > p.first) {
      l--;
      num[ar[l]]++;
      if (num[ar[l]] == 1) {
        pos = bit_summ(ar[l]) + 1;
        bit_update(ar[l] + 1, 1);
        update(0, N - 1, ar[l], 0, pos, true);
      }
    }
    while (r < p.second) {
      r++;
      num[ar[r]]++;
      if (num[ar[r]] == 1) {
        pos = bit_summ(ar[r]) + 1;
        bit_update(ar[r] + 1, 1);
        update(0, N - 1, ar[r], 0, pos, true);
      }
    }
    while (r > p.second) {
      num[ar[r]]--;
      if (num[ar[r]] == 0) {
        bit_update(ar[r] + 1, -1);
        update(0, N - 1, ar[r], 0, 0, false);
      }
      r--;
    }
    ans[ix] = st[0][0];
  }
  for (int i = 0; i < Q; i++) cout << ans[i] << "\n";
}
