#include <bits/stdc++.h>
using namespace std;
const long double pi = 3.1415926535897932384626433832795l;
template <typename T>
inline auto sqr(T x) -> decltype(x * x) {
  return x * x;
}
template <typename T1, typename T2>
inline bool umx(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T1, typename T2>
inline bool umn(T1& a, T2 b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
const int N = 30000;
const int M = 30000;
struct Input {
  int mod;
  int n, m;
  int a[N];
  int l[M], r[M];
  bool read() {
    if (!(cin >> n >> mod)) {
      return 0;
    }
    for (int i = int(0); i < int(n); ++i) {
      scanf("%d", &a[i]);
    }
    cin >> m;
    for (int i = int(0); i < int(m); ++i) {
      scanf("%d%d", &l[i], &r[i]);
      --l[i];
    }
    return 1;
  }
  void init(const Input& input) { *this = input; }
};
struct Data : Input {
  int ans[M];
  void write() {
    for (int i = int(0); i < int(m); ++i) {
      cout << ans[i] << endl;
    }
  }
  virtual void solve() {}
  virtual void clear() { *this = Data(); }
};
struct Solution : Data {
  static const int K = 12;
  static const int D = N / K + 1;
  int f[N + 10];
  int p[N], rev[N];
  int cnt[M];
  int hv[M];
  int msk[N + 1];
  int mb[1 << K], bt[2][1 << K], v[2][1 << K][2];
  void solve() {
    f[0] = 1;
    f[1] = 0;
    for (int i = int(0); i < int(N + 8); ++i) {
      f[i + 2] = (f[i] + f[i + 1]) % mod;
    }
    for (int i = int(0); i < int(n); ++i) {
      p[i] = i;
    }
    sort(p, p + n, [&](int i, int j) { return a[i] < a[j]; });
    ;
    for (int i = int(0); i < int(n); ++i) {
      rev[p[i]] = i;
    }
    for (int i = int(0); i < int(1 << K); ++i) {
      mb[i] = K;
      while (mb[i] >= 0 && !(i & (1 << mb[i]))) {
        --mb[i];
      }
    }
    memset(ans, 0, sizeof ans);
    memset(cnt, 0, sizeof cnt);
    memset(hv, -1, sizeof hv);
    for (int t = int(0); t < int(D); ++t) {
      if (t * K >= n) {
        break;
      };
      msk[0] = 0;
      for (int i = int(0); i < int(n); ++i) {
        msk[i + 1] = msk[i];
        if (rev[i] >= t * K && rev[i] < (t + 1) * K) {
          msk[i + 1] |= 1 << (rev[i] - t * K);
        }
      };
      memset(v, 0, sizeof v);
      memset(bt, 0, sizeof bt);
      for (int w = int(0); w < int(2); ++w) {
        for (int i = int(0); i < int(min(K, n - t * K)); ++i) {
          for (int q = int(0); q < int(1 << i); ++q) {
            if (i ? (a[p[t * K + i]] == a[p[t * K + i - 1]]) : w) {
              if (i) {
                v[w][q | (1 << i)][0] = v[w][q | (1 << (i - 1))][0];
                v[w][q | (1 << i)][1] = v[w][q | (1 << (i - 1))][1];
                bt[w][q | (1 << i)] = bt[w][q | (1 << (i - 1))];
              } else {
                v[w][q | (1 << i)][0] = v[w][q][0];
                v[w][q | (1 << i)][1] = v[w][q][1];
                bt[w][q | (1 << i)] = bt[w][q];
              }
            } else {
              v[w][q | (1 << i)][0] =
                  (v[w][q][0] + f[bt[w][q]] * (a[p[t * K + i]] % mod)) % mod;
              v[w][q | (1 << i)][1] =
                  (v[w][q][1] + f[bt[w][q] + 1] * (a[p[t * K + i]] % mod)) %
                  mod;
              bt[w][q | (1 << i)] = bt[w][q] + 1;
            }
          }
        }
      }
      for (int i = int(0); i < int(m); ++i) {
        int ttt = (hv[i] == -1) ? 0 : (a[p[hv[i]]] == a[p[t * K]]);
        int mmm = msk[r[i]] & ~msk[l[i]];
        ans[i] = (ans[i] + v[ttt][mmm][0] * f[cnt[i] + 2] +
                  v[ttt][mmm][1] * f[cnt[i] + 3]) %
                 mod;
        ;
        ;
        ;
        cnt[i] += bt[ttt][mmm];
        if (mb[mmm] != -1) {
          hv[i] = t * K + mb[mmm];
        }
      }
    }
  }
  void clear() { *this = Solution(); }
};
Solution sol;
int main() {
  ;
  cout.setf(ios::showpoint | ios::fixed);
  cout.precision(20);
  sol.read();
  sol.solve();
  sol.write();
  return 0;
}
