팩토리얼 곱 정리하기

피터는 조합론 문제를 풀고 있습니다. 긴 계산 끝에 그는 두 팩토리얼 곱의 비 형태인 다음 식을 얻었습니다.

$n!$ 은 $n$ 개의 원소를 나열하는 경우의 수를 나타내므로, 팩토리얼은 조합론 공식에 자주 등장합니다.

그런데 피터가 계산 과정에서 실수를 했을 수도 있습니다. 그는 결과가 정수여야 한다는 것을 알고 있으므로 먼저 이를 확인하려 합니다. 결과가 정수라면, 그는 이를 다음과 같은 팩토리얼 곱 형태로 정리하고자 합니다.

여기서 $r_i$ 는 모두 서로 다른 1보다 큰 정수이며 엄격히 감소하는 순서로 나열됩니다 ($r_i > r_{i+1} > 1$). 또한 모든 $s_i$ 와 $t$ 는 양의 정수입니다. 이러한 모든 표현 중에서 피터는 $r_1$ 이 가능한 한 큰 것을 원하고, 그중에서는 $s_1$ 이 가능한 한 큰 것을, 다시 그중에서는 $r_2$ 가 가능한 한 큰 것을, 이어서 $s_2$ 를, 이런 식으로 남은 $t$ 를 더 이상 이 형태로 표현할 수 없을 때까지 선택합니다. 피터는 $t$ 의 실제 값에는 관심이 없고, 결과의 팩토리얼 곱 부분만 알고 싶어 합니다.

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어집니다 ($1 \le n, m \le 1000$). 둘째 줄에 $n$ 개의 정수 $p_i$ 가 공백으로 구분되어 주어집니다 ($1 \le p_i \le 10\,000$). 셋째 줄에 $m$ 개의 정수 $q_i$ 가 공백으로 구분되어 주어집니다 ($1 \le q_i \le 10\,000$).

첫째 줄에 정수 $k$ 하나를 출력합니다.

• 두 팩토리얼 곱의 비가 정수가 아니면 $k = -1$ 을 출력합니다.
• 비가 정수이지만 요구된 형태로 표현할 수 없으면 $k = 0$ 을 출력합니다.
• 비를 위에서 설명한 형태로 표현할 수 있으면 $k > 0$ 을 출력하고, 이어서 $k$ 개의 줄을 출력합니다. 그중 $i$ 번째 줄에는 두 정수 $r_i$ 와 $s_i$ 를 공백으로 구분하여 출력합니다.