Factorial Simplification

Peter is working on a combinatorial problem. After a long derivation he obtained a formula that is a ratio of two products of factorials:

$$ \frac{p_1!,p_2! \dots p_n!}{q_1!,q_2! \dots q_m!} $$

Factorials show up often in combinatorics, since $n!$ counts the permutations of $n$ elements.

Peter may have made a mistake, though. He knows the result must be an integer, so he first wants to check that. If it is an integer, he wants to rewrite it as a product of factorials of the form

$$ r_1!^{,s_1}, r_2!^{,s_2} \dots r_k!^{,s_k}, t $$

where the $r_i$ are distinct integers greater than one written in strictly decreasing order ($r_i > r_{i+1} > 1$), and every $s_i$ and $t$ is a positive integer. Among all such representations Peter wants the one where $r_1$ is as large as possible; among those, the one where $s_1$ is as large as possible; among those, the one where $r_2$ is as large as possible; then $s_2$; and so on, until the remaining $t$ can no longer be written in this form. Peter does not care about the value of $t$; he only wants the factorial-product part of the result.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1000$). The second line contains $n$ integers $p_i$ ($1 \le p_i \le 10,000$) separated by spaces. The third line contains $m$ integers $q_i$ ($1 \le q_i \le 10,000$) separated by spaces.

On the first line print a single integer $k$.

• Print $k = -1$ if the ratio of the two factorial products is not an integer.
• Print $k = 0$ if the ratio is an integer but cannot be represented in the required form.
• Print $k > 0$ if the ratio can be represented as described. In that case print $k$ more lines; the $i$-th of them contains two integers $r_i$ and $s_i$ separated by a space.