P5881 【化学】实验

小 Z 紧张地坐在了一张化学实验桌前，进行着化学实验。 教室里又传来了一阵哀叹声： 我…我好像又错了…我能再试一次吗?

在她的面前，摆放着 $n$ 个试管。试管里装着不明液体。对于每种不明液体，有 $2$ 个已知的化学属性：$a$ 和 $b$。第 $i$ 种液体的两个属性值分别为 $a_i$ 和 $b_i$。 现在，老师给她布置了 $m$ 个实验。 对于每一次实验，有一个参照量 $x$（第 $i$ 次实验的参照量记作 $x_i$）。她需要把不明液体分成尽可能多的组，且满足：任意两种不同组的液体$i$和$j$， $\operatorname{gcsd(a_i,a_j)}$ 都不能大于 $x^2$。 其中 $\operatorname{gcsd}$ 代表他们的最大公约平方数。$k$是两个数的公约平方数，当且仅当满足以下两个条件： - $k$ 为这两个数的公约数； - $k$ 为完全平方数。 而最大公约平方数 $\operatorname{gcsd}$ 为所有满足条件的 $k$ 中的最大者。 形象的说， $\operatorname{gcsd}$ 可以理解成两个数的最大公约数的算术平方根的整数因式部分的平方。 例如： 求 $\operatorname{gcsd(24,64)}$，就是先求出 $24,64$ 的最大公约数，是 $8$ ，然后 $\sqrt 8=2\sqrt 2$，其整数因式是 $2$，所以 $\operatorname{gcsd(24,64)}=2^2=4$。 她还需要在分组数最多的情况下，使自己的实验得分最大。 实验得分的定义：对于每一种试剂，定义其得分 $c_i$ 为 $b_i$ 分解质因数之后最大的**指数**。 例如：$b_i=12=2^2\times 3^1$，$c_i=\max\{2,1\}=2$。 $b_i=90=2^1\times 3^2\times 5^1$，$c_i=\max\{1,2,1\}=2$。 而实验得分即为所有组内的 $c_i$ 的最大值之和。 当然，她的 $IQ$ 并不高，所以需要请求你的帮助。

第一行两个整数 $n,m$。 第二行 $n$ 个整数 $a_{1\dots n}$。 第三行 $n$ 个整数 $b_{1\dots n}$。 第四行 $m$ 个整数 $x_{1\dots m}$。

共 $m$ 行，对于第 $i$ 行，输出 $2$ 个整数：第 $i$ 次试验的组数和实验得分。

#### 样例解释 #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$。 当 $x=2$ 时，可分为三组：$\{1,2,4\},\{3\},\{5\}$。 实验得分为$\max\{1,2,3\}+\max\{1\}+\max\{1\}=5$。 ---------- #### 数据范围 **「本题采用捆绑测试」** | subtask | $n\le$ | $m\le$ | $a_i \le$ | $b_i\le$ | $x \le$ | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |:-----------:| | $1$ | $4$ | $6$ | $100$ | $4 \times 10^4$ | $100$ | $5$ | | $2$ | $8$ | $7$ | $20$ | $10^3$ | $10$ | $5$ | | $3$ |$20$ | $30$ | $50$ | $8 \times 10^3$ | $100$ | $10$ | | $4$ |$100$ | $60$ | $100$ | $4 \times 10^4$ | $10^3$ | $10$ | | $5$ |$5 \times 10^3$ | $110$ | $10^3$| $10^5$ | $4 \times 10^3$ | $10$ | | $6$ |$2 \times 10^4$ | $250$ | $3 \times 10^3$ | $10^6$ | $3 \times 10^3$ | $10$ | | $7$ |$ 5 \times 10^4$| $10^3$ | $10^4$ | $2 \times 10^7$ | $1.5 \times 10^4$ | $15$ | | $8$ |$10^5$ | $8 \times 10^3$ | $2 \times 10^4$ | $2 \times 10^7$ | $2.2 \times 10^4$ | $15$ | | $9$ |$2 \times 10^5$ | $2 \times 10^5$ | $4 \times 10^4$ | $2 \times 10^7$ | $3 \times 10^4$ | $20$ | 对于 $100\%$ 的数据： $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$。 我$\dots$我好像又错了$\dots$我能再试一次吗?