#include <bits/stdc++.h>
using namespace std;
inline int ri() {
  int x;
  scanf("%d", &x);
  return x;
}
template <typename T>
inline bool smax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
inline bool smin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
const int maxn = 30005;
int n, mod, m = 0;
int a[maxn], id[maxn];
int fib[maxn];
struct seg {
  int l, r, d, off;
  int x0, x1;
  seg *ls, *rs;
  seg(int l_, int r_)
      : l(l_), r(r_), d(0), off(0), ls(NULL), rs(NULL), x0(0), x1(0) {
    if (l < r) {
      int mid = (l + r) >> 1;
      ls = new seg(l, mid);
      rs = new seg(mid + 1, r);
    }
  }
  inline void shift(int x) {
    off += x;
    d += x;
    if (x > 0) {
      int tmp = (x0 * fib[x - 1] + x1 * fib[x]) % mod;
      x1 = (x0 * fib[x] + x1 * fib[x + 1]) % mod;
      x0 = tmp;
    } else if (x < 0) {
      x = -x;
      if (x % 2 == 0) {
        int tmp = (x0 * fib[x + 1] - x1 * fib[x]);
        x1 = (x1 * fib[x - 1] - x0 * fib[x]);
        x0 = tmp;
      } else {
        int tmp = (x1 * fib[x] - x0 * fib[x + 1]);
        x1 = (x0 * fib[x] - x1 * fib[x - 1]);
        x0 = tmp;
      }
      x0 %= mod;
      if (x0 < 0) x0 += mod;
      x1 %= mod;
      if (x1 < 0) x1 += mod;
    }
  }
  inline void down() {
    if (d == 0) return;
    if (ls) ls->shift(d);
    if (rs) rs->shift(d);
    d = 0;
  }
  void add(int pos, int x) {
    if (l == r) {
      x0 = (x0 + fib[off] * x) % mod;
      x1 = (x1 + fib[off + 1] * x) % mod;
      return;
    }
    down();
    int mid = (l + r) >> 1;
    if (mid < pos) {
      rs->add(pos, x);
    } else {
      ls->add(pos, x);
    }
    x0 = (ls->x0 + rs->x0);
    x1 = (ls->x1 + rs->x1);
    if (x0 >= mod) x0 -= mod;
    if (x1 >= mod) x1 -= mod;
    off = ls->off;
  }
  void move(int x, int lo, int hi) {
    if (x == 0) return;
    if (lo <= l && r <= hi) {
      shift(x);
      return;
    }
    down();
    int mid = (l + r) >> 1;
    if (lo <= mid) ls->move(x, lo, hi);
    if (hi > mid) rs->move(x, lo, hi);
    x0 = (ls->x0 + rs->x0);
    x1 = (ls->x1 + rs->x1);
    if (x0 >= mod) x0 -= mod;
    if (x1 >= mod) x1 -= mod;
    off = ls->off;
  }
} * tree;
struct query {
  int id, l, r;
} q[30000];
int res[30000];
int cnt[maxn];
inline void insert(int x) {
  if ((++cnt[id[x]]) == 1) {
    tree->move(1, id[x], m);
    tree->add(id[x], a[x] % mod);
  }
}
inline void remove(int x) {
  if ((--cnt[id[x]]) == 0) {
    tree->add(id[x], -a[x] % mod);
    tree->move(-1, id[x], m);
  }
}
int main() {
  scanf("%d%d", &n, &mod);
  vector<pair<int, int> > v;
  for (int i = 0; i < (n); i++) {
    scanf("%d", a + i);
    v.push_back(pair<int, int>(a[i], i));
  }
  sort(v.begin(), v.end());
  id[v[0].second] = 0;
  for (int i = (1); i < (v.size()); i++)
    if (v[i].first != v[i - 1].first) {
      id[v[i].second] = ++m;
    } else {
      id[v[i].second] = m;
    }
  fib[1] = fib[2] = 1;
  for (int i = (3); i < (maxn); i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
  int Q = ri();
  for (int i = 0; i < (Q); i++) {
    q[i].id = i;
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].l--;
    q[i].r--;
  }
  const int sqr = 300;
  sort(q, q + Q, [](query a, query b) {
    return a.l / sqr == b.l / sqr ? (((a.l / sqr) & 1) ? a.r > b.r : a.r < b.r)
                                  : a.l / sqr < b.l / sqr;
  });
  int L = q[0].l, R = q[0].l - 1;
  tree = new seg(0, m);
  for (int i = 0; i < (Q); i++) {
    while (R < q[i].r) insert(++R);
    while (L > q[i].l) insert(--L);
    while (R > q[i].r) remove(R--);
    while (L < q[i].l) remove(L++);
    res[q[i].id] = tree->x0;
  }
  for (int i = 0; i < (Q); i++) printf("%d\n", (res[i] % mod + mod) % mod);
  return 0;
}
