자와이 무기
시간 제한3초메모리 제한256 MB
세 소수 d1<=d2<=d3가 세 가지 제곱 마이너스 1 나눗셈 조건을 만족할 때, 사전순으로 k번째 세 쌍을 찾는다.
문제
옛날부터 자와이에게는 세 가지 무기로 이루어진 세트가 있었다. 레이저 검, 레이저 사브르, 그리고 빵에 버터를 바르는 레이저 나이프다(자와이가 배고파질 수도 있으니까).
하지만 이 무기는 평범한 무기가 아니라 자와이 무기이므로, 세트에 들어가는 물건의 길이에는 다음과 같은 제한이 붙었다.
- 나이프의 길이 d1, 사브르의 길이 d2, 검의 길이 d3은 모두 소수여야 한다.
- d1 ≤ d2 ≤ d3
- (d1 + d2)2 − 1은 d3으로 나누어떨어진다.
- (d2 + d3)2 − 1은 d1으로 나누어떨어진다.
- (d3 + d1)2 − 1은 d2로 나누어떨어진다.
"Dart Generics Industries"는 모든 자와이 무기 세트를 사전순 번호로 판매한다. 구체적으로, 모든 자와이 세트를 d1이 작은 순서대로, d1이 같으면 d2가 작은 순서대로, d1과 d2가 같으면 d3이 큰 순서대로 정렬한 뒤 1부터 무한대까지 번호를 매긴다. 그러면 주어진 k로 이 순서에서 k번째 세트를 살 수 있다.
자와이 Anykey는 k번째 세트를 사고 싶어 한다. 그의 무기 크기를 알려 주자.
입력
첫째 줄에 정수 k가 주어진다. (1 ≤ k ≤ 60000)
출력
k번째 세트에 들어 있는 무기 세 개의 크기를 작은 순서대로 출력한다.