题目描述

题目译自 XXX Olimpiada Informatyczna – III etap NWW

对于正整数序列 $(b_1, b_2, \ldots, b_k)$，我们用 $\operatorname{NWW}(b_1, b_2, \ldots, b_k)$ 表示其最小公倍数，即最小的正整数，它是序列中每个数的倍数。此外，定义序列的 $\operatorname{NWW}$-和，记为 $\operatorname{NWWSUMA}(b_1, b_2, \ldots, b_k)$，为序列所有连续子段最小公倍数的总和：

[ \operatorname{NWWSUMA}(b_1, b_2, \ldots, b_k) = \sum_{i=1}^{k} \sum_{j=i}^{k} \operatorname{NWW}(b_i, b_{i+1}, \ldots, b_j). ]

给定一个正整数序列 $(a_1, a_2, \ldots, a_n)$ 和正整数 $M$，请回答 $q$ 个关于该序列的查询。每个查询形式为：给定序列中的编号 $l$ 和 $r$，计算 $\operatorname{NWWSUMA}(a_l, a_{l+1}, \ldots, a_r)$。由于答案可能非常大，只需输出每个查询答案除以 $M$ 的余数。

---

输入格式

第一行包含三个整数 $n$, $q$, $M$ ($1 \leq n \leq 100000$, $1 \leq q \leq 300000$, $2 \leq M \leq 10^9$)，分别表示序列长度、查询数量和模数 $M$。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 1000000$)，表示序列的元素。

接下来的 $q$ 行描述查询，第 $i$ 行包含两个整数 $l_i$, $r_i$ ($1 \leq l_i \leq r_i \leq n$)，表示查询 $\operatorname{NWWSUMA}(a_{l_i}, a_{l_i+1}, \ldots, a_{r_i})$ 的值。

---

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示 $\operatorname{NWWSUMA}(a_{l_i}, a_{l_i+1}, \ldots, a_{r_i})$ 除以 $M$ 的余数。

---

样例

输入

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

输出

7
22
19
4

第一个查询涉及子段 $(1, 3)$，其 $\operatorname{NWW}$-和为：

[ \operatorname{NWWSUMA}(1, 3) = \operatorname{NWW}(1, 3) + \operatorname{NWW}(1) + \operatorname{NWW}(3) = 7. ]

第二个查询涉及子段 $(6, 4)$，其 $\operatorname{NWWSUMA}(6, 4) = 22$。

第三个查询涉及整个序列，其 $\operatorname{NWW}$-和为 $69$，因 $M=50$，输出 $69 \bmod 50 = 19$。

第四个查询涉及子段 $(4)$，其 $\operatorname{NWWSUMA}(4) = 4$。

---

附加样例

• $n=500$, $q=300000$, $M=15625$, $a_i=1000000$，$l_i, r_i$ 随机，所有答案为 $0$。
• $n=4$, $q=1$, $M=42$, $a_i=2$，$l_1=1$, $r_1=n$，答案为 $7$。
• $n=100000$, $q=1$, $M=2$, $a_i=i$，$l_1=50000$, $r_1=50010$，答案为 $1$。

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$n, q \leq 500$	12
2	$n \leq 500$	10
3	$q=1$	32
4	$n \leq 50000$, $q \leq 100000$	27
5	无附加限制	19