시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB115251024.390%

문제

유리수를 표현하기 위해 보통 분수를 사용한다. 분수 a/b에서 a를 분자, b를 분모라고 부르고, a와 b는 모두 정수이다. 분수에서 분모가 너무 큰 숫자이면 수식에서 다루기 힘들어진다. 그래서 수학자들은 분모 b가 매우 큰 분수 a/b가 있을 때, 이를 대신하여 분모가 작은 분수 a1/b1와 a2/b2를 사용한다, 여기서 a1/b1 ≤ a/b ≤ a2/b2이고 b1과 b2는 둘 다 특정한 정수 c보다 크지 않아야 한다. (즉, b1, b2 ≤ c).

분수 a1/b1과 a2/b2를 a/b의 근사치 분수 쌍이라고 하자. 수학자들은 근사치 분수 쌍들 중 두 분수의 차이(즉,  a2/b2 - a1/b1)가 최소가 되는 근사치 분수 쌍을 사용하기를 원한다. 수학자를 도와주기 위해, 주어진 분수에 대해 차이가 최소가 되는 근사치 분수 쌍을 찾는 프로그램을 작성하시오. 

입력

첫째 줄에 세 개의 정수 a, b, c가 주어진다.

출력

첫째 줄에 네 개의 정수 a1, b1, a2, b2를 출력한다. 여기서 a1/b1과 a2/b2는 주어진 분수의 근사치 분수 쌍들 중 그 차이가 최소인 것이어야 하고, a1과 b1이 서로소이고 a2와 b2가 서로소이어야 한다. 단, 값이 0인 분수는 항상 “0 1”을 출력한다.

제한

  • 0 ≤ a < b ≤ 2×109
  • 1 ≤ c ≤ 2×109

예제 입력 1

3 7 4

예제 출력 1

1 3 1 2

출처

  • 문제를 번역한 사람: author5
  • 데이터를 추가한 사람: wider93