题目描述

在得知的地球的位置后，三体人准备驾驶舰队奔赴地球，但是三体人的舰队加速的方式很特别，在它的控制器上有长度为 n 的整数序列，三体人可以选择一段特定的区间，将舰队直接从单位速度加速至这段区间中所有整数的乘积的倍，但是由于基础的物理学限制，在飞船将要加速 v 倍时，如果 v ≥ p，其速度就只会加速至v mod p倍（v mod p 的结果可能为 0），由于三体人想尽快的到达地球，他们给出了希望知道加速结果的 m 个区间的起点和终点？他们将这个信息告诉了叶文洁之后，统帅找到了你，希望你可以解答三体人的疑惑。

输入格式

从文件 acceleration.in 中读取数据。 输入共 m+2 行，第一行三个整数 n（n<=100,000），m（m<=100,000），p(p>0,且在 int 范围)，具体意义见题面， 第二行 n 个整数表示控制器上的整数序列，均在 int 范围， 第三行至第 m+2 行，每行两个数 l, r 分别表示询问的起点和终点。

输出格式

输出到文件 acceleration.out 中。 输出共 m 行，每行为一个整数，表示对一次询问的回答。

样例 #1

样例输入 #1

10 3 100
1 2 3 4 5 6 7 8 9 10
2 4
4 10
6 10

样例输出 #1

24
0
40

提示

数据范围： 对于 25%的数据，保证输入的 n, m<=1000。 对于 100%的数据，保证输入的 n, m<=100000，l 和 r 的范围同 n 且 l<=r。