Exact Fraction of a Float

Version: Phuoc Hung OJ Extended

Problem Statement

Given a real number $x$ parsed as a Python 3 float, find integers $p$ and $q>0$ with $x=\dfrac pq$ exactly for the stored binary value, in lowest terms. Do not use the ideal decimal fraction of the input text. Match Python x.as_integer_ratio().

Input

The only line contains finite real number $x$, parsed as Python 3 float.

Output

Print integers $p$ and $q$ on one line, separated by a space: numerator first, positive denominator second. The fraction must be reduced.

Subtasks

• Subtask 1 (100 points): $x$ is a finite Python float; the denominator must be positive.

Examples

Example 1

Input

0.5

Output

1 2

Explanation. The value $0.5=1/2$ is represented exactly; numerator $1$ and denominator $2$ are already coprime.

Example 2

Input

0.1

Output

3602879701896397 36028797018963968

Explanation. Decimal $0.1$ has no finite binary representation. The displayed fraction exactly represents the stored float, rather than the ideal value $1/10$.

Example 3

Input

1.25

Output

5 4

Explanation. Since $1.25=125/100=5/4$ and $5$ and $4$ are coprime, the output is 5 4.