Prime Partitioning

MCPlayer542 has devised a quirky method called "Prime Partitioning" while preparing a mysterious prime. He prepared n distinct numbers \(a_1, a_2, \ldots, a_n\) as test points and defined the prime score function for every positive integer \(x\) and indices \(l, r\) (with \(1 \le l \le r \le n\)) 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\le y \text{ and } \gcd(x,y)=1, \ -x\cdot y, & \text{if } x\neq 1 \text{ and } \gcd(x,y)=x, \ 0, & \text{otherwise.} \end{cases} ]

Here \(u\) is a parameter provided in each query. Notice that for any fixed test point \(y\), only a few values of \(x\) give a nonzero contribution. In fact, by analysing the four cases we can combine the summation for a fixed \(y\) as:

[ \sum_{x=1}^{10^6} f(x,y)=u\cdot \varphi(y)-y\cdot \sigma(y), ]

where \(\varphi(y)\) is Euler's totient function and \(\sigma(y)\) is the sum of divisors of \(y\). Therefore, the total score for the range \([l,r]\) becomes:

[ S(l,r)=\sum_{i=l}^{r} [u\cdot \varphi(a_i)-a_i\cdot \sigma(a_i)] = u\cdot \Bigl(\sum_{i=l}^{r} \varphi(a_i) \Bigr) - \Bigl(\sum_{i=l}^{r} a_i\cdot \sigma(a_i)\Bigr). ]

MCPlayer542 plans to run \(q\) queries. In each query, you are given an integer \(u\) and a starting index \(l\). For each query, determine the maximum total score \(S(l,r)\) over all \(r\) with \(l \le r \le n\) and the minimum index \(r\) that attains this maximum value.

Input Format: The first line contains two integers \(n\) and \(q\). The second line contains \(n\) distinct integers \(a_1, a_2, \ldots, a_n\). Each of the next \(q\) lines contains two integers \(u\) and \(l\).

Output Format: For each query, output two space-separated integers: the maximum total score and the minimum index \(r\) (with \(l\le r\le n\)) which attains the maximum score.

inputFormat

The input begins with a line containing two integers \(n\) and \(q\). The next line contains \(n\) distinct integers \(a_1, a_2, \ldots, a_n\). Each of the following \(q\) lines contains two integers \(u\) and \(l\), where \(u\) is the parameter for function \(f(x,y)\) and \(l\) is the starting index for the query.

n q
 a1 a2 ... an
u1 l1
u2 l2
... 
 uq lq

outputFormat

For each query, output a single line with two space‐separated integers: the maximum achievable total score and the minimum index \(r\) (such that \(l \le r \le n\)) at which this maximum is attained.

sample

3 2
2 3 5
10 1
5 2

22 3
-2 2