차이가 작은 분해

n을 서로 1 이하만큼 차이나는 양의 정수들의 곱으로 나타내는 모든 분해를 나열하고, 무한히 많으면 -1을 출력한다.

보통6정수론수학완전 탐색아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제

리디아는 수를 가지고 노는 것을 좋아한다. 오늘 리디아에게 양의 정수 nn이 하나 있고, 리디아는 이 수를 양의 정수의 곱으로 분해하려고 한다.

리디아는 크기가 비슷한 수를 좋아한다. 그래서 분해에 쓰인 수는 어느 두 개를 골라도 차이가 1 이하여야 하고, 분해에 쓰인 수를 모두 곱하면 nn이 되어야 한다. 두 분해는 원소 개수가 같고 한쪽을 재배열해 다른 쪽을 만들 수 있을 때 같은 분해로 본다.

오늘 리디아가 가지고 놀 수 있는 분해를 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 정수 nn이 주어진다. (1n10181 \le n \le 10^{18})

출력

분해가 무한히 많으면 첫째 줄에 1-1만 출력한다.

분해가 유한하면 첫째 줄에 분해의 개수를 출력한다. 다음 줄부터 분해를 한 줄에 하나씩 출력한다. 각 줄에는 그 분해의 원소 개수 kk를 먼저 출력하고, 이어서 원소 kk개를 작은 수부터 차례로 출력한다. 수와 수 사이는 공백 하나로 구분한다.

서로 다른 분해는 원소 개수가 항상 다르므로, 줄은 kk가 작은 것부터 큰 순서로 출력한다.