약수가 있는가?

시간 제한2초메모리 제한512 MB

요약

숫자 문자열이 주어질 때, 해당 문자열을 어떤 진법 B로 해석한 값이 합성수가 되도록 하는 진법 B와 1보다 큰 약수 X를 찾고, 둘 다 10^9 이하가 되게 하거나 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 문자열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

정보올림피아드 문제를 다루는 포럼에서 다음과 같은 캡차를 도입했다. 참가자에게 $N$ 자리 십진수 문자열(앞에 0이 없음)이 주어진다. 답으로, 주어진 기록이 이 진법에서 합성수(이를 $D$ 라 하자)가 되는 진법의 밑 $B$ 와, $1$ 보다 크고 $D$ 보다 작으면서 $D$ 의 약수인 수 $X$ 를 입력해야 한다.

이때 $B$ 와 $X$ 는 $10^9$ 를 넘지 않아야 한다.

주어진 십진수 문자열에 대해, 제약을 만족하는 $B$ 와 $X$ 의 쌍을 아무거나 하나 찾거나, 주어진 제약 안에 해가 존재하지 않는다고 답하라.

입력

입력은 0부터 9까지의 숫자로 이루어지고 0으로 시작하지 않으며 길이가 $3 \cdot 10^6$ 이하인 비어 있지 않은 문자열 하나로 구성된다.

출력

해가 존재하면 진법의 밑 $B$ 와 약수 $X$ 를 십진법으로 출력한다. 두 수는 모두 $2 \le B,X \le 10^9$ 를 만족해야 한다. 해가 존재하지 않으면 $-1$ 을 출력한다.

예제3

예제 1
입력
```
1
```
예상 출력
```
-1
```
예제 2
입력
```
4
```
예상 출력
```
10 2
```
예제 3
입력
```
19
```
예상 출력
```
11 2
```