题目描述

题目译自 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$。

附加样例

1. $n=500, q=300000, M=15625, a_i=1000000$，$l_i, r_i$ 随机，所有答案为 $0$。
2. $n=4, q=1, M=42, a_i=2$，$l_1=1, r_1=n$，答案为 $7$。
3. $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$