Description

Peter is working on a combinatorial problem. He has carried out quite lengthy derivations and got a resulting formula that is a ratio of two products of factorials like this:

This does not surprise Peter, since factorials appear quite often in various combinatorial formulae, because n! represents the number of transpositions of n elements — one of the basic combinatorial objects. However, Peter might have made a mistake in his derivations. He knows that the result should be an integer number and he needs to check this first. For an integer result Peter wants to simplify this formula to get a better feeling of its actual combinatorial significance. He wants to represent the same number as a product of factorials like this.

where all r_i

are distinct integer numbers greater than one in the descending order (r

_i

> r

_i+1

> 1), s

_i

and t are positive integers. Among all the possible representations in this form, Peter is interested in one where r

₁

is the largest possible number, among those in the one where s

₁

is the largest possible number; among those in the one where r

₂

is the largest possible number; among those in the one where s

₂

is the largest possible number; etc, until the remaining t cannot be further represented in this form. Peter does not care about the actual value of t. He wants to know what is the factorial-product part of his result.

Input

The first line of the input file contains two integer numbers n and m (1 <= n,m <= 1000). The second line of the input file contains n integer numbers pi (1 <= pi <= 10 000) separated by spaces. The third line of the input file contains m integer numbers qi (1 <= qi <= 10 000) separated by spaces.

Output

On the first line of the output write a single integer number k. Write k = -1 if the ratio of the given factorial products is not an integer. Write k = 0 if the ratio is an integer but it cannot be represented in the desired form. Write k > 0 followed by k lines if the ratio can be represented by a factorial product as described in the problem statement. On each of the following k lines write two integers r

_i

and s

_i

(for i = 1 ... k) separated by a space.

<table border="1" style="border-collapse: collapse" bordercolor="#000000" id="table1"><tbody><tr>
<td><b>#1</b></td><td>
1 2<br>
6<br>
4 4</td>
</tr>
<tr>
<td><b>#2</b></td><td>
1 2<br>
6<br>
3 4</td></tr>
<tr>
<td><b>#3</b></td><td>
4 2<br>
9 2 2 2<br>
3 4</td></tr>
</tbody></table>

<table border="1" style="border-collapse: collapse" bordercolor="#000000" id="table1"><tbody><tr>
<td><b>#1</b></td><td>
-1</td>
</tr>
<tr>
<td><b>#2</b></td><td>
0</td></tr>
<tr>
<td><b>#3</b></td><td>
2<br>
7 1<br>
2 2</td></tr>
</tbody></table>

Source

Northeastern Europe 2010