Problem Description

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

He then invented a method, which he named "Prime Score," although it's rather foolish.

He prepared \( n \) different 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) = \begin{cases} u - y, & \text{if } x = 1 \\ u, & \text{if } 1 < x \leq y, \gcd(x, y) = 1 \\ -x \cdot y, & \text{if } x \neq 1, \gcd(x, y) = x \\ 0, & \text{otherwise} \end{cases} \]

Prime numbers typically have a higher "Prime Score," but this doesn't seem to be very useful.

MCPlayer542 is now desperate and plans to test randomly, aiming to obtain the total score \( \sum_{i=1}^{10^6} score(i, l, r) \). He will conduct \( q \) tests, each time specifying \( u \) and \( l \), where \( u \) is a parameter for the function \( f(x, y) \).

For each query, he wants to know the maximum total score and the smallest \( r \) that achieves this maximum score.

Input Format

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

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) (\( 1 \leq a_i \leq 10^6 \)), separated by a single space, representing the test points.

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

Output Format

For each query, output a line with two numbers: the maximum total score and the smallest \( r_i \) (\( l_i \leq r_i \leq n \)), separated by a single space.

Sample Input and Output

Input Sample #1

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

Output Sample #1

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

Input Sample #2

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

Output Sample #2

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

Notes

In the first query of Sample 1, \( u_1 = 14, l_1 = 4 \). If we choose \( r_1 = 6 \), the final total score is \( \sum_{i=1}^{10^6} score(i, 4, 6) \). For example:
- \( 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 \), \( score(i, 4, 6) = 0 + 0 + 0 = 0 \).

Thus, 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 achieved for other values of \( r_1 \), so the answer is \( 55 \), and the smallest \( r_1 \) that achieves this is \( 6 \).

见题面 Input 部分

见题面 Output 部分