For a sequence of positive integers $(b_1, b_2, \dots, b_k)$, we denote by $\text{LCM}(b_1, b_2, \dots, b_k)$ the least common multiple of the numbers in this sequence — that is, the smallest positive integer that is a multiple of every number in the sequence. Furthermore, we define the LCM-sum of a sequence $(b_1, b_2, \dots, b_k)$, denoted by $\text{LCMSUM}(b_1, b_2, \dots, b_k)$, as the sum of the least common multiples of all contiguous fragments of this sequence:

$$\text{LCMSUM}(b_1, b_2, \dots, b_k) = \sum_{i=1}^{k} \sum_{j=i}^{k} \text{LCM}(b_i, b_{i+1}, \dots, b_j)$$

You are given a sequence of positive integers $(a_1, a_2, \dots, a_n)$ and a positive integer $M$. Answer $q$ queries about this sequence. Each query is of the following form: given indices $l$ and $r$ in the sequence $a$, what is $\text{LCMSUM}(a_l, a_{l+1}, \dots, a_r)$? Since the answers to the queries can be very large, it is sufficient to provide the remainder of the division of the answer by $M$ for each query.

Input

The first line of input contains three integers $n, q, M$ ($1 \le n \le 100\,000$, $1 \le q \le 300\,000$, $2 \le M \le 10^9$), representing the length of the sequence, the number of queries, and the integer $M$, respectively. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1\,000\,000$), which are the consecutive elements of the sequence.

The next $q$ lines of input describe the queries; the $i$-th of these lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$), representing a query for the value of $\text{LCMSUM}(a_{l_i}, a_{l_i+1}, \dots, a_{r_i})$.

Output

You should output exactly $q$ lines; the $i$-th line should contain the remainder of the division of $\text{LCMSUM}(a_{l_i}, a_{l_i+1}, \dots, a_{r_i})$ by $M$.

Examples

Input 1

4 4 50
6 4 1 3
3 4
1 2
1 4
2 2

Output 1

7
22
19
4

Note

The first query concerns the fragment $(1, 3)$. Its LCM-sum is: $\text{LCMSUM}(1, 3) = \text{LCM}(1, 3) + \text{LCM}(1) + \text{LCM}(3) = 7$. The second query concerns the fragment $(6, 4)$; we have $\text{LCMSUM}(6, 4) = 22$. The third query concerns the entire input sequence. Its LCM-sum is $69$. However, since $M = 50$, the remainder of the division of the LCM-sum by $50$, which is $19$, should be printed.

Subtasks