题目描述

为了悄悄准备一个神秘的质数，MCPlayer542 伤透了脑筋。

随后他发明了一种聪明愚蠢的办法，并起名为“质数分”。

他准备了 $n$ 个不同的数 $a_1,\ a_2,\ \ldots,\ a_n$ 作为测试点，并定义“质数分” $score(x,l,r)$ 如下：

$$score(x,l,r)=\sum_{i=l}^r{f(x,a_i)}$$

其中

$$f(x,y)=\left\{\begin{array}{rcl}u-y, & x=1 \\ u, & 1<x\le y,\ \gcd(x,y)=1 \\ -x\cdot y, & x\neq 1,\ \gcd(x,y)=x \\ 0, & \text{otherwise} \end{array}\right. $$

可见质数的“质数分”通常会比较高但还是没什么卵用。

于是 MCPlayer542 急了，现在他只想暴力乱测，并得到一个得分和 $\sum_{i=1}^{10^6}{score(i,l,r)}$。他打算测试 $q$ 次，每次测试给定 $u$ 和 $l$，其中 $u$ 为函数 $f(x,y)$ 的参数。

对于每次询问，他想知道所能得到的最大得分和以及能得到这个最大得分和的最小 $r$ 是多少。

输入格式

输入数据的第一行包含两个整数 $n,\ q$ ($1\le n,\ q\le 5\times 10^5$)，用单个空格分隔。

第二行包含 $n$ 个整数 $a_1,\ a_2,\ \ldots,\ a_n$ ($1\le a_i\le 10^6$)，用单个空格分隔，表示测试点的数据。

接下来 $q$ 行，每行两个整数 $u_i,\ l_i$ ($1\le u_i \le 1.8\times 10^7,\ 1\le l_i\le n$)，用单个空格分隔，表示一次询问。

输出格式

对每个询问输出一行两个数，即对应询问的最大得分和以及能获得该得分的最小 $r_i$ ($l_i\le r_i\le n$)，用单个空格分隔。

10 7
10 9 2 1 5 3 10 10 1 8
14 4
17 5
13 10
16 1
12 4
16 6
16 3

55 6
60 6
-68 10
-58 6
41 6
20 6
79 6

6 8
3 7 7 10 8 9
21 1
20 4
21 3
21 5
21 1
21 2
21 2
21 5

170 3
-100 4
70 3
-27 6
170 3
140 3
140 3
-27 6

提示

在样例 1 的第一个询问中，$u_1=14,\ l_1=4$。若我们选择 $r_1=6$，则最后的得分和为 $\sum_{i=1}^{10^6}{score(i,4,6)}$。其中：

• $score(1,4,6)=13+9+11=33$；
• $score(2,4,6)=0+14+14=28$；
• $score(3,4,6)=0+14-9=5$；
• $score(4,4,6)=0+14+0=14$；
• $score(5,4,6)=0-25+0=-25$；
• $i$ 取其他值时均有 $score(i,4,6)=0+0+0=0$。

故 $r_1=6$ 时得分和为 $33+28+5+14-25=55$。

可以证明在 $r_1$ 取其他值时无法得到更大的得分和，故答案为 $55$，且能达成的最小 $r_1$ 为 $6$。