Maximal Group Partitioning and Score Maximization

In this problem, you are given (n) test tubes, each containing an unknown liquid. For the (i)-th liquid, you are given two integers (a_i) and (b_i) representing two chemical properties. In addition, there are (m) experiments. For the (i)-th experiment a reference value (x_i) is provided.

You need to partition the (n) liquids into as many groups as possible while satisfying the following condition:

For any two liquids (i) and (j) that belong to different groups, their (\operatorname{gcsd}(a_i,a_j)) must not exceed (x^2) (where (x) is the reference value for that experiment).

The function (\operatorname{gcsd}(a, b)) is defined as the largest perfect square that divides both (a) and (b). More formally, a positive integer (k) is called a common square divisor of (a) and (b) if:

1. (k) divides both (a) and (b), and
2. (k) is a perfect square (i.e. (k= t^2) for some integer (t)).

Then (\operatorname{gcsd}(a, b)) is the maximum such (k). For example, consider (\operatorname{gcsd}(24, 64)): The greatest common divisor of (24) and (64) is (8), and (\sqrt{8}=2\sqrt{2}); the integer part is (2) so (\operatorname{gcsd}(24,64)=2^2=4).

A useful observation is that if we define a function

[ f(a)=\prod_{p^e \parallel a} p^{\lfloor e/2 \rfloor}, ]

then it can be shown that

[ \operatorname{gcsd}(a, b) = \bigl(\gcd(f(a), f(b))\bigr)^2. ]

Thus, the grouping condition, (\operatorname{gcsd}(a_i,a_j) \le x^2), is equivalent to

[ \gcd(f(a_i), f(a_j)) \le x. ]

In other words, if (\gcd(f(a_i), f(a_j)) > x) then liquids (i) and (j) must be in the same group.

For each experiment the score is determined as follows. For each liquid, define its score (c_i) as the maximum exponent in the prime factorization of (b_i). For example:

• If (b_i=12=2^2\times 3^1), then (c_i=2).
• If (b_i=90=2^1\times 3^2\times 5^1), then (c_i=2).

After grouping, the experiment score is the sum of the maximum (c_i) over all groups. Note that you must first maximize the number of groups (by splitting liquids as much as possible without violating the condition) and then, among all such partitions, maximize the experiment score (i.e. the sum of maximum scores in each group).

Your task is to help her determine, for each experiment, the maximum number of groups and the maximum experiment score achievable under the conditions.

1. Input: \(n\) liquids and \(m\) experiments, followed by \(n\) lines of \(a_i\) and \(b_i\), and then \(m\) lines each containing a reference value \(x_i\).
2. Output: For each experiment, output two integers: the maximum number of groups and the maximum experiment score.

Constraints

It is guaranteed that all input values are positive integers. You may assume that (n) is small enough for an (O(n^2)) solution per experiment to pass.

inputFormat

The first line contains two integers (n) and (m) denoting the number of liquids and experiments.

Each of the next (n) lines contains two integers (a_i) and (b_i) ((1 \le i \le n)).

Each of the next (m) lines contains one integer (x_i), the reference value for that experiment.

outputFormat

For each experiment, output two space-separated integers in a single line: the maximum number of groups and the maximum experiment score.

sample

3 1
24 12
64 90
45 30
1

2 3