#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= 1000000007;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % 1000000007;
    a = a * a % 1000000007;
  }
  return res;
}
int gcd(int x, int y) {
  while (y) {
    int t = x % y;
    x = y;
    y = t;
  }
  return x;
}
int ans[30010], fib[30010], blo[30010];
struct query {
  int l, r, id;
  query() {}
  query(int l, int r, int id) : l(l), r(r), id(id) {}
  friend bool operator<(const query &a, const query &b) {
    return blo[a.l] == blo[b.l] ? (blo[a.l] & 1 ? a.r > b.r : a.r < b.r)
                                : a.l < b.l;
  }
};
query q[30010];
int s1[30010 << 2], s0[30010 << 2], sz[30010 << 2], cnt[30010];
vector<int> v;
int n, m, Q, a[30010];
void push_up(int rt) {
  sz[rt] = sz[(rt << 1)], s1[rt] = s1[(rt << 1)], s0[rt] = s0[(rt << 1)];
  (s0[rt] += s0[((rt << 1) | 1)] * fib[sz[(rt << 1)] + 1] +
             s1[((rt << 1) | 1)] * fib[sz[(rt << 1)]]) %= m;
  if (sz[(rt << 1)])
    (s1[rt] += s0[((rt << 1) | 1)] * fib[sz[(rt << 1)]] +
               s1[((rt << 1) | 1)] * fib[sz[(rt << 1)] - 1]) %= m;
  else
    s1[rt] = s1[((rt << 1) | 1)];
  sz[rt] += sz[((rt << 1) | 1)];
}
void update(int x, int val, int ll, int rr, int rt) {
  if (ll == rr) {
    (s1[rt] += val * v[x - 1]) %= m;
    (s0[rt] += val * v[x - 1]) %= m;
    sz[rt] += val;
    return;
  }
  if (x <= ((ll + rr) / 2))
    update(x, val, ll, ((ll + rr) / 2), (rt << 1));
  else
    update(x, val, ((ll + rr) / 2) + 1, rr, ((rt << 1) | 1));
  push_up(rt);
}
void add(int x) {
  if (!cnt[a[x]]++) update(a[x], 1, 1, n, 1);
}
void del(int x) {
  if (!--cnt[a[x]]) update(a[x], -1, 1, n, 1);
}
int main() {
  scanf("%d%d", &n, &m);
  fib[0] = 0, fib[1] = 1;
  for (int i = 2; i <= n; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % m;
  for (int i = 0; i <= n; i++) blo[i] = i / 200;
  v.clear();
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), v.push_back(a[i]);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; i++)
    a[i] = 1 + lower_bound(v.begin(), v.end(), a[i]) - v.begin();
  scanf("%d", &Q);
  for (int i = 0; i < Q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    q[i] = query(l, r, i);
  }
  sort(q, q + Q);
  int l = 1, r = 1;
  add(1);
  for (int i = 0; i < Q; i++) {
    while (r < q[i].r) add(++r);
    while (l > q[i].l) add(--l);
    while (r > q[i].r) del(r--);
    while (l < q[i].l) del(l++);
    ans[q[i].id] = s1[1];
  }
  for (int i = 0; i < Q; i++) printf("%d\n", (ans[i] + m) % m);
  return 0;
}
