#include <bits/stdc++.h>   using namespace std;   const int N = 3e4;   int n, aa[N + 2], fib[N + 2], con[N + 2], m;   void compress() {     vector<int> v;     for (int i = 1; i <= n; i++) v.push_back(aa[i]);     sort(v.begin(), v.end());     v.erase(unique(v.begin(), v.end()), v.end());     map<int, int> mp;     for (int i = 0; i < v.size(); i++) {       mp[v[i]] = i + 1;       con[i + 1] = v[i] % m;     }     for (int i = 1; i <= n; i++) aa[i] = mp[aa[i]];   }   bool vs[N + 2];   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cin >> n >> m;     for (int i = 1; i <= n; i++) cin >> aa[i];     compress();     fib[1] = 1;     fib[2] = 1;     for (int i = 3; i <= 30000; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % m;     int q;     cin >> q;     while (q--) {       int l, r;       cin >> l >> r;       for (int i = l; i <= r; i++) vs[aa[i]] = 1;       long long ans = 0;       int cnt = 1;       for (int i = 1; i <= 30000; i++) {         if (vs[i]) {           ans += con[i] * fib[cnt++];           vs[i] = 0;         }       }       cout << ans % m <<   n ;     }     return 0;   }   