#include <bits/stdc++.h>
using namespace std;
int N, M = 1 << 30, A[30000], B[30000], NB, Q, QL[30000], QR[30000],
       order[30000], ans[30000];
struct mint {
  int x;
  mint(const int& x = 0) : x(x % M) {}
  friend mint operator+(const mint& a, const mint& b) {
    return (a.x + b.x) % M;
  }
  friend mint operator-(const mint& a, const mint& b) {
    return (a.x - b.x) % M;
  }
  friend mint operator*(const mint& a, const mint& b) {
    return (a.x * b.x) % M;
  }
  operator int() const { return x; }
};
struct vec {
  mint x, y;
  vec(const mint& x = 0, const mint& y = 0) : x(x), y(y) {}
  friend vec operator+(const vec& a, const vec& b) {
    return {a.x + b.x, a.y + b.y};
  }
  friend vec operator-(const vec& a, const vec& b) {
    return {a.x - b.x, a.y - b.y};
  }
};
struct mat {
  mint a, b, c, d;
  mat(const mint& a = 1, const mint& b = 0, const mint& c = 0,
      const mint& d = 1)
      : a(a), b(b), c(c), d(d) {}
  friend mat operator*(const mat& a, const mat& b) {
    return {a.a * b.a + a.b * b.c, a.a * b.b + a.b * b.d, a.c * b.a + a.d * b.c,
            a.c * b.b + a.d * b.d};
  }
  friend vec operator*(const mat& a, const vec& b) {
    return {a.a * b.x + a.b * b.y, a.c * b.x + a.d * b.y};
  }
} fib[30000 + 1];
struct seg {
  int NN, V[30000];
  bool dirty[1 << 17];
  pair<vec, int> nodes[1 << 17];
  seg(int N) {
    for (NN = 1; NN < N;) NN <<= 1;
    memset(V, 0, sizeof V);
  }
  inline pair<vec, int> combine(const pair<vec, int>& a,
                                const pair<vec, int>& b) {
    if (!a.second) return b;
    if (!b.second) return a;
    return {a.first + fib[a.second] * b.first, a.second + b.second};
  }
  int _x, _c;
  void update(int x, int c) {
    V[x] += c;
    if (c == 1 && V[x] == 1) _x = x, _c = c, _update(1, 0, NN - 1);
    if (c == -1 && V[x] == 0) _x = x, _c = c, _update(1, 0, NN - 1);
  }
  void _update(int i, int l, int r) {
    if (l == r) {
      if (_c == 1)
        nodes[i] = {{B[l], 0}, 1};
      else
        nodes[i] = {{0, 0}, 0};
    } else {
      if (_x <= (l + r) / 2)
        _update(2 * i, l, (l + r) / 2);
      else
        _update(2 * i + 1, (l + r) / 2 + 1, r);
      dirty[i] = true;
    }
  }
  void get(int i, int l, int r) {
    if (!dirty[i] || l == r) return;
    get(2 * i, l, (l + r) / 2);
    get(2 * i + 1, (l + r) / 2 + 1, r);
    nodes[i] = combine(nodes[2 * i], nodes[2 * i + 1]);
    dirty[i] = false;
  }
  pair<vec, int> query() {
    get(1, 0, NN - 1);
    return nodes[1];
  }
};
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < (N); ++i) scanf("%d", &A[i]);
  fib[1] = {1, 1, 1, 0};
  for (int i = 2; i <= N; ++i) fib[i] = fib[i - 1] * fib[1];
  copy(A, A + N, B);
  sort(B, B + N);
  NB = unique(B, B + N) - B;
  for (int i = 0; i < (N); ++i) A[i] = lower_bound(B, B + NB, A[i]) - B;
  scanf("%d", &Q);
  for (int i = 0; i < (Q); ++i) scanf("%d%d", &QL[i], &QR[i]), --QL[i], --QR[i];
  iota(order, order + Q, 0);
  int BLOCK = 200;
  sort(order, order + Q, [=](const int& i, const int& j) {
    int bi = QL[i] / BLOCK, bj = QL[j] / BLOCK;
    if (bi != bj)
      return bi < bj;
    else
      return QR[i] < QR[j];
  });
  int l = 0, r = 0;
  seg tree(NB);
  tree.update(A[0], 1);
  for (int i = 0; i < (Q); ++i) {
    while (l > QL[order[i]]) tree.update(A[--l], 1);
    while (r < QR[order[i]]) tree.update(A[++r], 1);
    while (l < QL[order[i]]) tree.update(A[l++], -1);
    while (r > QR[order[i]]) tree.update(A[r--], -1);
    ans[order[i]] = tree.query().first.x;
  }
  for (int i = 0; i < (Q); ++i) printf("%d\n", ans[i]);
  return 0;
}
