Obsessed with Hatsune Miku

Input

The first line contains two integers $n$ and $q$ ( $1 \leq n, q \leq 1 0^{6}$ 1 \le n, q \le 10^6)—the number of fans and the number of scenarios.

The next line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $0 \leq a_{i} \leq 1 0^{6}$ 0 \le a_i \le 10^6)—the number of Miku dolls each fan currently has.

Each of the next $q$ lines contains two integers $x$ and $k$ ( $1 \leq x \leq 1 0^{9}$ 1 \le x \le 10^9, $1 \leq k \leq 1 0^{6}$ 1 \le k \le 10^6). Note: $k$ is a divisor of $x$ for every scenario.

Output

For each scenario, output two integers—the maximum number of obsessed fans that can be achieved, and the minimum number of operations required to achieve that, on a new line.

Examples

Example 1

Loading

Note

In the first query, $x = 4$ x = 4, $k = 2$ k = 2. Fans $2$ and $3$ are already obsessed since $a_{2} \geq 4$ a_2 \ge 4 and $a_{3} \geq 4$ a_3 \ge 4. By taking one block ( $2$ dolls) from fan $3$ and giving it to fan $1$ ( $i = 3$ i=3, $j = 1$ j=1), all three fans become obsessed. Thus, the answer is 3 obsessed fans, 1 operation.

In the second query, $x = 4$ x=4, $k = 1$ k=1. Fans $2$ and $3$ are already obsessed. By moving $1$ doll from fan $3$ to fan $1$ ( $i = 3$ i=3, $j = 1$ j=1), all three reach at least $4$ dolls. So, the answer is 3 obsessed fans, 1 operation.

In the third query, $x = 3$ x=3, $k = 3$ k=3. No operations are necessary; all fans are already obsessed. The answer is 3 obsessed fans, 0 operations.

In the fourth query, $x = 13$ x=13, $k = 13$ k=13. Only fan $3$ is initially obsessed. By moving one block ( $13$ dolls) from fan $3$ to fan $1$ ( $i = 3$ i=3, $j = 1$ j=1), and one block from fan $3$ to fan $2$ ( $i = 3$ i=3, $j = 2$ j=2), all three become obsessed. The answer is 3 obsessed fans, 2 operations.

In the fifth query, $x = 13$ x=13, $k = 1$ k=1. Only fan $3$ is initially obsessed; fans $1$ and $2$ have deficits of $13 - 3$ 13-3 and $13 - 9$ 13-9 dolls, respectively, totaling $14$ dolls. By transferring $1$ doll at a time from fan $3$ to fans $1$ and $2$ , $14$ operations are needed. The answer is 3 obsessed fans, 14 operations.

In the sixth query, $x = 24$ x=24, $k = 2$ k=2. Only fan $3$ is initially obsessed. To make two fans obsessed, we focus on fans $2$ and $3$ , whose blocks sum to $19 + 4 = 23$ 19+4=23; one more block ( $2$ dolls) is needed. By moving $2$ dolls from fan $3$ to fan $2$ ( $i = 3$ i=3, $j = 2$ j=2), the answer is 2 obsessed fans, 1 operation.

In the seventh query, $x = 40$ x=40, $k = 10$ k=10. The total number of blocks is $3$ , which is insufficient for any fan to become obsessed. The answer is 0 obsessed fans, 0 operations.

Scoring

Subtask $1$ ( $5$ points): $1 \leq n, q \leq 10$ 1 \le n, q \le 10
Subtask $2$ ( $5$ points): $1 \leq n, q \leq 100$ 1 \le n, q \le 100
Subtask $3$ ( $10$ points): $1 \leq n, q \leq 1000$ 1 \le n, q \le 1000
Subtask $4$ ( $20$ points): $a_{1} = a_{2} = \dots = a_{n}$ a_1 = a_2 = \ldots = a_n
Subtask $5$ ( $20$ points): $k = x$ k = x
Subtask $6$ ( $20$ points): $k = 1$ k = 1
Subtask $7$ ( $20$ points): $1 \leq k \leq 100$ 1 \le k \le 100
Subtask $8$ ( $50$ points): $1 \leq n, q \leq 1 0^{5}$ 1 \le n, q \le 10^5; $a_{i}, k \leq 1 0^{4}$ a_i, k \le 10^4
Subtask $9$ ( $50$ points): $1 \leq n, q, a_{i}, k \leq 3 \cdot 1 0^{5}$ 1 \le n, q, a_i, k \le 3 \cdot 10^5
Subtask $10$ ( $100$ points): No additional constraints.