#include <bits/stdc++.h>
using namespace std;
unsigned int n, m, q, sq;
unsigned int *a, *fib;
struct query {
  unsigned int l, r, ind;
} * queries;
struct node {
  unsigned int key, prior, mdkey, val, prevVal, size;
  node *l, *r;
  node(){};
  node(unsigned int key, unsigned int prior, unsigned int mdkey)
      : key(key),
        prior(prior),
        mdkey(mdkey),
        prevVal(0),
        val(mdkey),
        size(1),
        l(NULL),
        r(NULL){};
};
unsigned int calcVal(node* t) {
  if (t == NULL) return 0;
  return t->val;
}
unsigned int calcPrevVal(node* t) {
  if (t == NULL) return 0;
  return t->prevVal;
}
unsigned int calcSize(node* t) {
  if (t == NULL)
    return 0;
  else
    return t->size;
}
void mergeT(node*& t, node* l, node* r) {
  if (l == NULL)
    t = r;
  else if (r == NULL)
    t = l;
  else if (l->prior > r->prior)
    mergeT(l->r, l->r, r), t = l;
  else
    mergeT(r->l, l, r->l), t = r;
  if (t == NULL) return;
  unsigned int ind = calcSize(t->l) + 1;
  t->size = ind + calcSize(t->r);
  unsigned int temp = calcVal(t->r);
  unsigned int tempPrev = calcPrevVal(t->r);
  t->val = (calcVal(t->l) + t->mdkey * fib[ind] + tempPrev * fib[ind] +
            temp * fib[ind + 1]) %
           m;
  t->prevVal = (calcPrevVal(t->l) + t->mdkey * fib[ind - 1] +
                tempPrev * fib[ind - 1] + temp * fib[ind]) %
               m;
}
void split(node* t, unsigned int key, node*& l, node*& r) {
  if (t == NULL)
    return void(l = r = NULL);
  else if (t->key > key)
    split(t->l, key, l, t->l), r = t;
  else
    split(t->r, key, t->r, r), l = t;
  unsigned int ind = calcSize(t->l) + 1;
  t->size = ind + calcSize(t->r);
  unsigned int temp = calcVal(t->r);
  unsigned int tempPrev = calcPrevVal(t->r);
  t->val = (calcVal(t->l) + t->mdkey * fib[ind] + tempPrev * fib[ind] +
            temp * fib[ind + 1]) %
           m;
  t->prevVal = (calcPrevVal(t->l) + t->mdkey * fib[ind - 1] +
                tempPrev * fib[ind - 1] + temp * fib[ind]) %
               m;
}
bool compare1(query q1, query q2) {
  return (q1.l / sq == q2.l / sq ? q1.r < q2.r : q1.l < q2.l);
}
void Solve() {
  scanf("%d%d", &n, &m);
  mt19937 rnd(123);
  a = new unsigned int[n];
  fib = new unsigned int[n + 1];
  node** atree = new node*[n];
  unordered_map<unsigned int, unsigned int> z;
  for (unsigned int i = 0; i < (n); ++i) {
    scanf("%d", &a[i]);
    atree[i] = new node(a[i], rnd(), a[i] % m);
    z.insert(make_pair(a[i], 0));
  }
  fib[0] = 0, fib[1] = 1;
  for (unsigned int i = 2; i <= n; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % m;
  scanf("%d", &q);
  sq = (unsigned int)sqrt(3.0 * n);
  queries = new query[q];
  unsigned int* answers = new unsigned int[q];
  for (unsigned int i = 0; i < (q); ++i)
    scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].l--, queries[i].r--,
        queries[i].ind = i;
  sort(queries, queries + q, compare1);
  unsigned int l = queries[0].l, r = l;
  node* t = atree[l];
  z[a[l]]++;
  for (unsigned int i = 0; i < (q); ++i) {
    while (queries[i].l < l) {
      l--;
      auto itz = z.find(a[l]);
      if (itz->second == 0) {
        node *tl, *tr, *it = atree[l];
        split(t, a[l], tl, tr);
        mergeT(t, tl, it);
        mergeT(t, t, tr);
      }
      itz->second++;
    }
    while (queries[i].r > r) {
      r++;
      auto itz = z.find(a[r]);
      if (itz->second == 0) {
        node *tl, *tr, *it = atree[r];
        split(t, a[r], tl, tr);
        mergeT(t, tl, it);
        mergeT(t, t, tr);
      }
      itz->second++;
    }
    while (queries[i].l > l) {
      auto itz = z.find(a[l]);
      itz->second--;
      if (itz->second == 0) {
        node *tl, *tr, *it;
        split(t, a[l], tl, tr);
        split(tl, a[l] - 1, tl, it);
        mergeT(t, tl, tr);
      }
      l++;
    }
    while (queries[i].r < r) {
      auto itz = z.find(a[r]);
      itz->second--;
      if (itz->second == 0) {
        node *tl, *tr, *it;
        split(t, a[r], tl, tr);
        split(tl, a[r] - 1, tl, it);
        mergeT(t, tl, tr);
      }
      r--;
    }
    answers[queries[i].ind] = calcVal(t);
  }
  for (unsigned int i = 0; i < (q); ++i) printf("%d\n", answers[i]);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie();
  Solve();
  return 0;
}
