Problem Description

To secretly prepare a mysterious prime number, MCPlayer542 racked his brains.

Then he invented a clever stupid method and named it “Prime Score”.

He prepared $n$ distinct numbers $a_1,\ a_2,\ \ldots,\ a_n$ as test points, and defined the “Prime Score” $score(x,l,r)$ as follows:

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

where

$$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.$$

As you can see, the “Prime Score” of a prime number is usually relatively high but still useless.

So MCPlayer542 panicked. Now he only wants to brute force test randomly and obtain a total score $\sum_{i=1}^{10^6}{score(i,l,r)}$. He plans to test $q$ times. Each test gives $u$ and $l$, where $u$ is the parameter in the function $f(x,y)$.

For each query, he wants to know the maximum total score he can get, and the smallest $r$ that can achieve this maximum total score.

Input Format

The first line of the input contains two integers $n,\ q$ ($1\le n,\ q\le 5\times 10^5$), separated by a single space.

The second line contains $n$ integers $a_1,\ a_2,\ \ldots,\ a_n$ ($1\le a_i\le 10^6$), separated by single spaces, representing the testdata of the test points.

The next $q$ lines each contain two integers $u_i,\ l_i$ ($1\le u_i \le 1.8\times 10^7,\ 1\le l_i\le n$), separated by a single space, representing one query.

Output Format

For each query, output one line with two numbers: the maximum total score for the query and the smallest $r_i$ ($l_i\le r_i\le n$) that can achieve this score, separated by a single space.

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

Hint

In the first query of Sample 1, $u_1=14,\ l_1=4$. If we choose $r_1=6$, then the final total score is $\sum_{i=1}^{10^6}{score(i,4,6)}$. Here:

• $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$;
• for other values of $i$, we have $score(i,4,6)=0+0+0=0$.

Therefore, when $r_1=6$ the total score is $33+28+5+14-25=55$.

It can be proven that no larger total score can be obtained for other values of $r_1$. Therefore the answer is $55$, and the smallest $r_1$ that achieves it is $6$.

Translated by ChatGPT 5