#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e4 + 5;
int mod, n, m, a[maxn], b[maxn], c[maxn], used[maxn], block, ans[maxn];
bool vis[maxn];
struct query {
  int l, r, id;
  bool operator<(const query &a) const {
    if (l / block != a.l / block) return l / block < a.l / block;
    return r != a.r ? r < a.r : l < a.l;
  }
} Q[maxn];
struct segtree {
  int node[maxn << 2][2][3];
  void build(int rt, int l, int r) {
    memset(node[rt], 0, sizeof(node[rt]));
    node[rt][0][0] = node[rt][1][1] = 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
  }
  void update(int rt, int l, int r, int x, int k) {
    if (l == r) {
      if (k) {
        node[rt][0][0] = node[rt][0][1] = node[rt][1][0] = 1;
        node[rt][1][1] = 0;
        node[rt][0][2] = node[rt][1][2] = c[x];
      } else {
        memset(node[rt], 0, sizeof(node[rt]));
        node[rt][0][0] = node[rt][1][1] = 1;
      }
      return;
    }
    int mid = (l + r) >> 1;
    x <= mid ? update(rt << 1, l, mid, x, k)
             : update(rt << 1 | 1, mid + 1, r, x, k);
    node[rt][0][0] = (node[rt << 1][0][0] * node[rt << 1 | 1][0][0] +
                      node[rt << 1][0][1] * node[rt << 1 | 1][1][0]) %
                     mod;
    node[rt][0][1] = (node[rt << 1][0][0] * node[rt << 1 | 1][0][1] +
                      node[rt << 1][0][1] * node[rt << 1 | 1][1][1]) %
                     mod;
    node[rt][0][2] =
        (node[rt << 1][0][0] * node[rt << 1 | 1][0][2] +
         node[rt << 1][0][1] * node[rt << 1 | 1][1][2] + node[rt << 1][0][2]) %
        mod;
    node[rt][1][0] = (node[rt << 1][1][0] * node[rt << 1 | 1][0][0] +
                      node[rt << 1][1][1] * node[rt << 1 | 1][1][0]) %
                     mod;
    node[rt][1][1] = (node[rt << 1][1][0] * node[rt << 1 | 1][0][1] +
                      node[rt << 1][1][1] * node[rt << 1 | 1][1][1]) %
                     mod;
    node[rt][1][2] =
        (node[rt << 1][1][0] * node[rt << 1 | 1][0][2] +
         node[rt << 1][1][1] * node[rt << 1 | 1][1][2] + node[rt << 1][1][2]) %
        mod;
  }
} tree;
void add(int x) {
  if (++used[x] == 1) tree.update(1, 1, m, x, 1);
}
void del(int x) {
  if (--used[x] == 0) tree.update(1, 1, m, x, 0);
}
void work(int x) {
  if (vis[x]) {
    vis[x] = false;
    del(a[x]);
  } else {
    vis[x] = true;
    add(a[x]);
  }
}
int main() {
  while (~scanf("%d%d", &n, &mod)) {
    block = sqrt(n + 0.5);
    for (int i = 1; i <= n; ++i) {
      scanf("%d", a + i);
      b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= m; ++i) c[i] = b[i] % mod;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    tree.build(1, 1, m);
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
      scanf("%d%d", &Q[i].l, &Q[i].r);
      Q[i].id = i;
    }
    sort(Q, Q + q);
    memset(vis, 0, sizeof(vis));
    memset(used, 0, sizeof(used));
    int l = Q[0].l, r = Q[0].r;
    for (int i = l; i <= r; ++i) work(i);
    ans[Q[0].id] = tree.node[1][1][2];
    for (int i = 1; i < q; ++i) {
      while (l < Q[i].l) work(l++);
      while (l > Q[i].l) work(--l);
      while (r < Q[i].r) work(++r);
      while (r > Q[i].r) work(r--);
      ans[Q[i].id] = tree.node[1][1][2];
    }
    for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
  }
  return 0;
}
