对于一个正整数序列 $(b_1, b_2, \dots, b_k)$，我们用 $\text{NWW}(b_1, b_2, \dots, b_k)$ 表示这些数的最小公倍数，即能被序列中每个数整除的最小正整数。此外，我们定义序列 $(b_1, b_2, \dots, b_k)$ 的 NWW-和，记为 $\text{NWWSUMA}(b_1, b_2, \dots, b_k)$，为该序列所有连续子段的最小公倍数之和：

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

给定一个正整数序列 $(a_1, a_2, \dots, a_n)$ 和一个正整数 $M$。请回答关于该序列的 $q$ 个查询。每个查询的形式如下：给定序列 $a$ 中的下标 $l$ 和 $r$，求 $\text{NWWSUMA}(a_l, a_{l+1}, \dots, a_r)$ 的值。由于查询的答案可能非常大，你只需要输出每个查询的答案对 $M$ 取模后的余数。

输入格式

第一行包含三个整数 $n, q, M$ ($1 \le n \le 100\,000, 1 \le q \le 300\,000, 2 \le M \le 10^9$)，分别表示序列长度、查询次数以及模数 $M$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1\,000\,000$)，即序列的元素。 接下来的 $q$ 行描述查询；第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)，表示对 $\text{NWWSUMA}(a_{l_i}, a_{l_i+1}, \dots, a_{r_i})$ 的查询。

输出格式

输出共 $q$ 行；第 $i$ 行应包含 $\text{NWWSUMA}(a_{l_i}, a_{l_i+1}, \dots, a_{r_i})$ 对 $M$ 取模后的余数。

样例

输入 1

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

输出 1

7
22
19
4

说明

第一个查询涉及片段 $(1, 3)$。其 NWW-和为： $\text{NWWSUMA}(1, 3) = \text{NWW}(1, 3) + \text{NWW}(1) + \text{NWW}(3) = 7$。 第二个查询涉及片段 $(6, 4)$；有 $\text{NWWSUMA}(6, 4) = 22$。 第三个查询涉及整个输入序列。其 NWW-和为 $69$。但由于 $M = 50$，输出应为 NWW-和除以 $50$ 的余数，即 $19$。

子任务

测试集分为以下子任务。每个子任务的测试数据由一组或多组独立的测试用例组成。