Factorial Simplification

Time limit1sMemory limit128 MB

Summary

Given a ratio of products of factorials, determine if it is an integer and greedily decompose it into a canonical product of factorial powers with maximal bases and exponents in order.

Level: Hard8 of 10
Topics: Math, Number theory, Greedy
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples4

Example 1
Input
```
4 2
9 2 2 2
3 4
```
Expected output
```
2
7 1
2 2
```
Example 2
Input
```
1 2
6
4 4
```
Expected output
```
-1
```
Example 3
Input
```
1 2
6
3 4
```
Expected output
```
0
```
Example 4
Input
```
1 1
5
1
```
Expected output
```
1
5 1
```