为了悄悄准备一个神秘的质数，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$ 是多少。
## Input
输入数据的第一行包含两个整数 $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$)，用单个空格分隔，表示一次询问。
## Output
对每个询问输出一行两个数，即对应询问的最大得分和以及能获得该得分的最小 $r_i$ ($l_i\le r_i\le n$)，用单个空格分隔。
[samples]
## Note
在样例 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$。