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≤30000)− 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≤30000).

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.