Description

In front of her, there are $n$ test tubes. Each test tube contains an unknown liquid. For each kind of unknown liquid, there are $2$ known chemical attributes: $a$ and $b$. The two attribute values of the $i$-th liquid are $a_i$ and $b_i$.

Now, the teacher assigns her $m$ experiments.

For each experiment, there is a reference value $x$ (the reference value of the $i$-th experiment is denoted as $x_i$). She needs to divide the unknown liquids into as many groups as possible, such that: for any two liquids $i$ and $j$ in different groups, $\operatorname{gcsd(a_i,a_j)}$ must not be greater than $x^2$.

Here, $\operatorname{gcsd}$ denotes the greatest common square divisor. $k$ is a common square divisor of two numbers if and only if it satisfies both of the following:

• $k$ is a common divisor of the two numbers;
• $k$ is a perfect square.

The greatest common square divisor $\operatorname{gcsd}$ is the maximum $k$ among all $k$ that satisfy the conditions.

Intuitively, $\operatorname{gcsd}$ can be understood as: take the greatest common divisor of the two numbers, take its square root, keep only the integer factor part, and then square it back.

For example:

To compute $\operatorname{gcsd(24,64)}$, first compute the greatest common divisor of $24$ and $64$, which is $8$. Then $\sqrt 8=2\sqrt 2$. Its integer factor is $2$, so $\operatorname{gcsd(24,64)}=2^2=4$.

She also needs, under the condition that the number of groups is maximized, to maximize her experiment score.

Definition of the experiment score: for each reagent, define its score $c_i$ as the largest exponent in the prime factorization of $b_i$.

For example: $b_i=12=2^2\times 3^1$, so $c_i=\max\{2,1\}=2$.

$b_i=90=2^1\times 3^2\times 5^1$, so $c_i=\max\{1,2,1\}=2$.

The experiment score is the sum, over all groups, of the maximum $c_i$ within each group.

Of course, her $IQ$ is not very high, so she needs to ask for your help.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers $a_{1\dots n}$.

The third line contains $n$ integers $b_{1\dots n}$.

The fourth line contains $m$ integers $x_{1\dots m}$.

Output Format

Output $m$ lines. For the $i$-th line, output $2$ integers: the number of groups and the experiment score for the $i$-th experiment.

5 5
36 72 4 9 16
2 4 6 8 10
2 3 4 5 6

3 5
4 7
4 7
4 7
5 8

Hint

Sample Explanation #1

$b_1=2=2^1,c_1=1$.

$b_2=4=2^2,c_2=2$.

$b_3=6=2^1\times 3^1,c_3=\max\{1,1\}=1$.

$b_4=8=2^3,c_4=3$.

$b_5=10=2^1\times 5^1,c_5=\max\{1,1\}=1$.

When $x=2$, it can be divided into three groups: $\{1,2,4\},\{3\},\{5\}$.

The experiment score is $\max\{1,2,3\}+\max\{1\}+\max\{1\}=5$.

Constraints

"This problem uses bundled testdata."

For $100\%$ of the data:

$1 \le n,m \le 2\times 10^5$, $2 \le a_i \le 4\times 10^4$, $2 \le b_i \le 2\times 10^7$, $2 \le x \le 3\times 10^4$.

I... I think I made a mistake again... Can I try one more time?

Translated by ChatGPT 5