Reducing Fractions

Description:

Input:

The first input line contains two space-separated integers n, m (1 ≤ n, m ≤ 10⁵) that show how many numbers the first set (the numerator) and the second set (the denominator) contain, correspondingly.

The second line contains n space-separated integers: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁷) — the numbers that are multiplied to produce the numerator.

The third line contains m space-separated integers: b₁, b₂, ..., b_m (1 ≤ b_i ≤ 10⁷) — the numbers that are multiplied to produce the denominator.

Output:

Print the answer to the problem in the form, similar to the form of the input data. The number of values in the sets you print n_out, m_out must satisfy the inequality 1 ≤ n_out, m_out ≤ 10⁵, and the actual values in the sets a_out, i and b_out, i must satisfy the inequality 1 ≤ a_out, i, b_out, i ≤ 10⁷.

Separate the values in the lines by spaces. The printed fraction must be reduced, that is, there mustn't be such integer x (x > 1), that the numerator and the denominator of the printed fraction are divisible by x. If there are several matching answers, print any of them.

Sample Input:

3 2
100 5 2
50 10

Sample Output:

2 3
2 1
1 1 1

Sample Input:

4 3
2 5 10 20
100 1 3

Sample Output:

1 1
20
3

Note:

In the first test sample the numerator equals 1000, the denominator equals 500. If we reduce fraction 1000/500 by the greatest common divisor of the numerator and the denominator (by 500), we obtain fraction 2/1.

In the second test sample the numerator equals 2000, the denominator equals 300. If we reduce fraction 2000/300 by the greatest common divisor of the numerator and the denominator (by 100), we obtain fraction 20/3.