#include <bits/stdc++.h>
using namespace std;
const int MAXK = 3;
const int MAXN = 30005;
map<int, int> Mp;
int V[MAXN], Cnt, cnt[MAXN];
int N, M, A[MAXN], B[MAXN];
int Q, stq, L, R, Ans[MAXN];
struct Matr {
  int a[MAXK][MAXK];
} I, It[MAXN];
Matr cheng(Matr A, Matr B) {
  Matr rt;
  memset(rt.a, 0, sizeof(rt.a));
  for (int i = 1; i <= 2; i++)
    for (int j = 1; j <= 2; j++)
      for (int k = 1; k <= 2; k++)
        rt.a[i][j] = (rt.a[i][j] + A.a[i][k] * B.a[k][j]) % M;
  return rt;
}
struct que {
  int l, r, id;
} q[MAXN];
struct Node {
  int l, r, cnt, siz, sum0, sum1;
} s[MAXN * 8];
bool cmp(que A, que B) {
  return A.l / stq == B.l / stq ? A.r < B.r : A.l < B.l;
}
void Prepare() {
  I.a[1][1] = 0;
  I.a[1][2] = 1;
  I.a[2][1] = 1;
  I.a[2][2] = 1;
  It[0].a[1][1] = 1;
  It[0].a[1][2] = 0;
  It[0].a[2][1] = 0;
  It[0].a[2][2] = 1;
  for (int i = 1; i <= N + 1; i++) It[i] = cheng(It[i - 1], I);
}
void Push_Up(int rt) {
  s[rt].cnt = s[rt * 2].cnt + s[rt * 2 + 1].cnt;
  s[rt].siz = s[rt * 2].siz + s[rt * 2 + 1].siz;
  int u = s[rt * 2].cnt;
  s[rt].sum0 = (s[rt * 2].sum0 + s[rt * 2 + 1].sum0 * It[u].a[1][1] +
                s[rt * 2 + 1].sum1 * It[u].a[1][2]) %
               M;
  s[rt].sum1 = (s[rt * 2].sum1 + s[rt * 2 + 1].sum0 * It[u + 1].a[1][1] +
                s[rt * 2 + 1].sum1 * It[u + 1].a[1][2]) %
               M;
}
void Build(int rt, int l, int r) {
  s[rt].l = l;
  s[rt].r = r;
  s[rt].cnt = s[rt].siz = 0;
  s[rt].sum0 = s[rt].sum1 = 0;
  if (l == r) return;
  int mid = (l + r) / 2;
  Build(rt * 2, l, mid);
  Build(rt * 2 + 1, mid + 1, r);
}
void Insert(int rt, int p, int val) {
  if (s[rt].r < p || s[rt].l > p) return;
  if (s[rt].l == s[rt].r) {
    if (s[rt].siz == 0) {
      s[rt].cnt++;
      s[rt].sum0 = V[p] % M;
      s[rt].sum1 = V[p] % M;
    }
    s[rt].siz += val;
    if (s[rt].siz == 0) {
      s[rt].cnt--;
      s[rt].sum0 = 0;
      s[rt].sum1 = 0;
    }
    return;
  }
  Insert(rt * 2, p, val);
  Insert(rt * 2 + 1, p, val);
  Push_Up(rt);
}
void Add(int x) { Insert(1, Mp[A[x]], 1); }
void Remove(int x) { Insert(1, Mp[A[x]], -1); }
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; i++) scanf("%d", &A[i]), B[i] = A[i];
  sort(B + 1, B + N + 1);
  Prepare();
  for (int i = 1; i <= N; i++) {
    if (!Mp[B[i]]) {
      Mp[B[i]] = ++Cnt;
      V[Cnt] = B[i];
    }
  }
  scanf("%d", &Q);
  stq = sqrt(Q);
  for (int i = 1; i <= Q; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
  Build(1, 1, Cnt);
  sort(q + 1, q + Q + 1, cmp);
  L = R = 1;
  Add(1);
  for (int i = 1; i <= Q; i++) {
    while (L < q[i].l) Remove(L++);
    while (L > q[i].l) Add(--L);
    while (R < q[i].r) Add(++R);
    while (R > q[i].r) Remove(R--);
    Ans[q[i].id] = s[1].sum0;
  }
  for (int i = 1; i <= Q; i++) printf("%d\n", Ans[i]);
}
