Fibonacci-ish II

Yash is finally tired of computing the length of the longest Fibonacci-ish sequence. He now plays around with more complex things such as Fibonacci-ish potentials.

Fibonacci-ish potential of an array a _i is computed as follows:

1. Remove all elements j if there exists i < j such that a _i = a _j.
2. Sort the remaining elements in ascending order, i.e. a ₁ < a ₂ < … < a _n.
3. Compute the potential as P(a) = a ₁·F ₁ + a ₂·F ₂ + … + a _n·F _n, where F _i is the i-th Fibonacci number (see notes for clarification).

You are given an array a _i of length n and q ranges from l _j to r _j. For each range j you have to compute the Fibonacci-ish potential of the array b _i, composed using all elements of a _i from l _j to r _j inclusive. Find these potentials modulo m.

Input

The first line of the input contains integers of n and m (1 ≤ n, m ≤ 30 000) — the length of the initial array and the modulo, respectively.

The next line contains n integers a _i (0 ≤ a _i ≤ 10⁹) — elements of the array.

Then follow the number of ranges q (1 ≤ q ≤ 30 000).

Last q lines contain pairs of indices l _i and r _i (1 ≤ l _i ≤ r _i ≤ n) — ranges to compute Fibonacci-ish potentials.

Output

Print q lines, i-th of them must contain the Fibonacci-ish potential of the i-th range modulo m.

Example

input

5 10
2 1 2 1 2
2
2 4
4 5

output

3
3

Note

For the purpose of this problem define Fibonacci numbers as follows:

1. F ₁ = F ₂ = 1.
2. F _n = F _n - 1 + F _n - 2 for each n > 2.

In the first query, the subarray [1,2,1] can be formed using the minimal set {1,2}. Thus, the potential of this subarray is 1*1+2*1=3.

#include <bits/stdc++.h>

using namespace std;

#define real REAL

const int N = 200010;

const int BLOCK = 250;

int m;
int from[N], to[N], res[N];
pair <int, int> ev[N];
int real[N], a[N];
int id[N];

inline bool cmp(int x, int y) {
int u = from[x] / BLOCK;
int v = from[y] / BLOCK;
if (u != v) {
return u < v;
  }
  return to[x] < to[y];
}

int a11[N], a12[N], a13[N];
int a21[N], a22[N], a23[N];

void build(int x, int l, int r) {
  a11[x] = 1; a12[x] = 0; a13[x] = 0;
  a21[x] = 0; a22[x] = 1; a23[x] = 0;
  if (l < r) {
    int y = (l + r) >> 1;
build(x + x, l, y);
build(x + x + 1, y + 1, r);
}
}

void modify(int x, int l, int r, int pos, int action) {
if (l == r) {
if (action == 1) {
a11[x] = 1; a12[x] = 1; a13[x] = real[pos];
a21[x] = 1; a22[x] = 0; a23[x] = 0;
} else {
a11[x] = 1; a12[x] = 0; a13[x] = 0;
a21[x] = 0; a22[x] = 1; a23[x] = 0;
}
return;
}
int y = (l + r) >> 1;
if (pos <= y) {
    modify(x + x, l, y, pos, action);
  } else {
    modify(x + x + 1, y + 1, r, pos, action);
  }
  // gather
  a11[x] = (a11[x + x] * a11[x + x + 1] + a12[x + x] * a21[x + x + 1]) % m;
  a12[x] = (a11[x + x] * a12[x + x + 1] + a12[x + x] * a22[x + x + 1]) % m;
  a21[x] = (a21[x + x] * a11[x + x + 1] + a22[x + x] * a21[x + x + 1]) % m;
  a22[x] = (a21[x + x] * a12[x + x + 1] + a22[x + x] * a22[x + x + 1]) % m;

  a13[x] = (a11[x + x] * a13[x + x + 1] + a12[x + x] * a23[x + x + 1] + a13[x + x]) % m;
  a23[x] = (a21[x + x] * a13[x + x + 1] + a22[x + x] * a23[x + x + 1] + a23[x + x]) % m;
}

int t;
int have[N];
int OPS;

void add(int what) {
  if (have[what] == 0) {
    OPS++;
    modify(1, 0, t - 1, what, 1);
  }
  have[what]++;
}

void del(int what) {
  have[what]--;
  if (have[what] == 0) {
    OPS++;
    modify(1, 0, t - 1, what, 0);
  }
}

int main() {
  int n;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &ev[i].first);
    ev[i].second = i;
  }
  sort(ev, ev + n);
  t = -1;
  for (int i = 0; i < n; i++) {
    if (i == 0 || ev[i].first != ev[i - 1].first) {
      t++;
      real[t] = ev[i].first % m;
    }
    a[ev[i].second] = t;
  }
  t++;
  for (int i = 0; i < t; i++) {
    have[i] = 0;
  }
  build(1, 0, t - 1);
  int tt;
  scanf("%d", &tt);
  for (int qq = 0; qq < tt; qq++) {
    scanf("%d %d", from + qq, to + qq);
    from[qq]--; to[qq]--;
    res[qq] = 0;
    id[qq] = qq;
  }
  sort(id, id + tt, cmp);
  int ll = from[0], rr = from[0] - 1;
  OPS = 0;
  for (int qq = 0; qq < tt; qq++) {
    while (rr > to[id[qq]]) {
del(a[rr]);
rr--;
}
while (ll < from[id[qq]]) {
      del(a[ll]);
      ll++;
    }
    while (rr < to[id[qq]]) {
      rr++;
      add(a[rr]);
    }
    while (ll > from[id[qq]]) {
ll--;
add(a[ll]);
}
res[id[qq]] = a13[1];
//    if ((qq + 1) % 500 == 0) cerr << qq+1 << " processed, OPS = " << OPS << endl;
  }
  for (int qq = 0; qq < tt; qq++) {
    printf("%d\n", (res[qq] % m + m) % m);
  }
//  cerr << clock() << " ms" << endl;
  return 0;
}