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.

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.

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