Description

On social media, it is common to see polls and their results about whether people agree with a certain viewpoint. For example, if $1498$ people support it and $902$ oppose it, then the ratio of support to opposition can be written simply as $1498:902$.

However, most people would not be satisfied if the results were presented this way, because the numbers in the ratio are too large and it is hard to see the relationship at a glance. For the example above, if the ratio is written as $5:3$, although there is some error compared with the true result, it still reflects the poll result fairly accurately and is more intuitive.

Given the number of supporters $A$, the number of opponents $B$, and an upper bound $L$, please reduce $A$ to $B$ into $A'$ to $B'$ under the conditions that $A'$ and $B'$ are both no greater than $L$ and $A'$ and $B'$ are coprime (the greatest common divisor of the two integers is $1$), such that $\dfrac{A'}{B'} \ge \dfrac{A}{B}$ and the value of $\dfrac{A'}{B'} - \dfrac{A}{B}$ is as small as possible.

Input Format

One line containing three integers $A,B,L$, separated by a single space, representing the number of supporters, the number of opponents, and the upper bound.

Output Format

One line containing two integers $A',B'$, separated by a single space, representing the simplified ratio.

1498 902 10

5 3

Hint

For $100\%$ of the testdata, $1 \le A \le 10^6, 1 \le B \le 10^6, 1 \le L \le 100, \dfrac{A}{B} \le L$.

Translated by ChatGPT 5