22904번 - 오렌지 수 서브태스크스페셜 저지

영국의 수학자 하디와 인도의 수학자 라마누잔의 일화를 아는가? 하디가 라마누잔에게 "오는 길에 탄 택시의 번호가 $1729$인데 별 특징이 없는 수 같아."라고 말했더니, 라마누잔은 "아니, $1729$는 두 세제곱수의 합으로 표현되는 방식이 두 가지뿐인 가장 작은 수야."라고 답했다고 전해진다. $1729 = 9^3 + 10^3 = 12^3 + 1^3$과 같이 표현된다.

오늘 코드포스 라운드에 참가한 이환이는 "내 레이팅이 $2259$가 되었는데 별 특징이 없는 수 같아."라고 말했다. 그러자 다니엘은 "아니, $2259$의 자릿수의 합은 $18$이고, 제곱해도 $5103081$이라 자릿수의 합이 $18$로 서로 같아."라고 답했다. 이 성질을 신기하게 여긴 이환이는 $2259$를 오렌지 수라고 이름 붙이고, 다니엘에게 정수 $K$에 대해 자릿수의 합이 $K$이고 제곱한 수의 자릿수의 합도 $K$인 자연수가 있는지 물었다. 다니엘을 도와 이런 수들을 찾아 주자!

첫 줄에 정수 $K$가 주어진다.

자연수 $N$의 각 자릿수를 모두 더한 값을 $S(N)$이라고 하자. $S(N)$은 10진법에서 정의된다.

$S(N)=S(N^2)=K$를 만족하는 자연수 $N$ 세 개를 찾아, 한 줄에 하나씩 출력하여라. 만약 그러한 $N$이 여러 개 존재한다면 아무거나 세 개를 출력해도 좋다. 단, $N$은 10의 배수가 아니어야 한다.

만약 그러한 $N$이 존재하지 않는다면 하나의 정수 $-1$을 출력해야 한다. 조건을 만족하는 $N$이 존재한다면 최소한 세 개는 존재함이 보장된다.

• $10^3 \le K \le 10^4$
• 각 수 $N$에 대해 $0 < N < 10^{10^5}$를 만족해야 한다. (즉, $N$은 10만 자리 이하여야 한다)
• 각 수는 10의 배수가 아니어야 한다.
• 각 수는 서로 달라야 한다.