유리수와 무리수

유리수는 두 정수의 비로 나타낼 수 있는 수이다. 소수 $p$에 대해, $\sqrt{p}$와 같은 유리수는 존재하지 않는다는 것이 정수론의 기본 정리 중 하나이다. 이런 수를 무리수라고 한다. 또한 $\sqrt{p}$에 임의로 가까운 유리수가 존재한다는 것도 알려져 있다.

이제 양의 정수 $n$이 주어졌을 때, $n$ 이하인 두 양의 정수의 비로 나타낼 수 있는 모든 유리수의 집합 $Q_n$을 정의하자. 예를 들어 $Q_4$는 11개의 유리수 {1/1, 1/2, 1/3, 1/4, 2/1, 2/3, 3/1, 3/2, 3/4, 4/1, 4/3}의 집합이다. 2/2, 2/4, 3/3, 4/2, 4/4는 각각 1/1, 1/2, 1/1, 2/1, 1/1과 같으므로 여기에 포함되지 않는다.

여러분의 임무는 두 정수 $p$와 $n$을 읽고 두 유리수 $x/y$와 $u/v$를 출력하는 프로그램을 작성하는 것이다. 여기서 $u/v < \sqrt{p} < x/y$이고 $u/v$와 $x/y$ 사이에 $Q_n$의 다른 원소가 없어야 한다. $n$이 $\sqrt{p}$보다 크면 이런 유리수 쌍은 항상 존재한다.

입력은 각 줄에 소수 $p$와 정수 $n$ 두 양의 정수가 다음 형식으로 주어진다.

p n

두 수는 공백으로 구분된다. $p$와 $n$은 10000보다 작고, $n$은 $\sqrt{p}$보다 크다고 가정할 수 있다. 입력의 끝은 두 개의 0으로 이루어진 줄로 표시된다.

각 입력 줄에 대해 두 유리수 $x/y$와 $u/v$($x/y > u/v$)를 공백으로 구분하여 다음 형식으로 한 줄에 출력한다.

x/y u/v

두 유리수는 기약분수여야 한다. 예를 들어 6/14와 15/3은 허용되지 않는다. 이들은 각각 3/7과 5/1로 약분되어야 한다.