密码分数 (find)

题目描述

一台古老的密码终端给出了一个最简真分数 $\frac{N}{D}$，其中 $1 \le N<D$ 且 $\gcd(N,D)=1$。终端还给出了一个上界 $R$。

你需要在所有满足下面条件的分数中，找出与 $\frac{N}{D}$ 最接近的一个：

1. 分子、分母都是正整数，且都在区间 $[1, R]$ 中；
2. 该分数是真分数，即分子小于分母；
3. 该分数是最简分数；
4. 该分数不能与给定的 $\frac{N}{D}$ 完全相同。

请输出找到的分数的分子和分母。

输入格式

在文件 find.in 中读入。 第一行包含两个用空格隔开的正整数 $N,\ D$，表示给定分数的分子和分母。 第二行包含一个正整数 $R$，表示候选分数的分子与分母均必须属于 $[1, R]$。

输出格式

在文件 find.out 中输出。 输出两个用空格隔开的正整数，分别表示答案分数的分子和分母。

样例

输入数据1

2 3
300

输出数据1

199 299

输入数据2

2 3
32767

输出数据2

21845 32767

提示

数据范围与提示

样例 1 解释： 第 $1$ 盏灯与第 $2$ 盏灯在三个时刻的状态依次都是 $1,0,1$，因此可以输出 1 2。

数据范围

对于部分的数据，$R \le 300$。 对于部分的数据，$R \le 3000$。 对于全部的数据，$1 \le R \le 100000$，$1 \le N<D<100000$。