#include <bits/stdc++.h>   using namespace std;   int F[30030];   int n;   int mod;   int a[30030], id[30030];   int nxt[30030];   bool cmp(int i, int j) { return a[i] < a[j]; }   int m;   struct pnt {     int l, r, i;     pnt(int l = 0, int r = 0, int i = 0) : l(l), r(r), i(i){};   } q[30030];   bool operator<(pnt a, pnt b) { return b.l != a.l ? a.l < b.l : a.r < b.r; }   int answer[30030];   int calc(int l, int r) {     int s = 0, m = 0;     for (int j, i = 1; i <= n; i++) {       j = id[i];       if (j >= l && j <= r) {         s = (s + F[++m] * a[j]) % mod;         i = nxt[i];       }     }     return s;   }   int main() {     scanf( %d %d , &n, &mod);     F[1] = F[2] = 1 % mod;     for (int i = 3; i <= n; i++) {       F[i] = (F[i - 1] + F[i - 2]) % mod;     }     for (int i = 1; i <= n; i++) {       scanf( %d , a + i);       id[i] = i;     }     sort(id + 1, id + n + 1, cmp);     nxt[n] = n;     for (int j = n - 1; j >= 1; j--) {       if (a[id[j]] == a[id[j + 1]]) {         nxt[j] = nxt[j + 1];       } else {         nxt[j] = j;       }     }     for (int j = 1; j <= n; j++) {       a[j] %= mod;     }     scanf( %d , &m);     for (int i = 1; i <= m; i++) {       scanf( %d %d , &q[i].l, &q[i].r);       q[i].i = i;     }     sort(q + 1, q + m + 1);     for (int i = 1; i <= m; i++) {       if (i > 1 && q[i].l == q[i - 1].l && q[i].r == q[i - 1].r) {         answer[q[i].i] = answer[q[i - 1].i];       } else {         answer[q[i].i] = calc(q[i].l, q[i].r);       }     }     for (int i = 1; i <= m; i++) {       printf( %d n , answer[i]);     }     return 0;   }   