Fraction Reduction

Problem Source

https://codeforces.com/gym/103447/problem/D

Problem Description

Everyone knows what it means for two fractions to be equivalent: we say $\frac{a}{b}$ and $\frac{p}{q}$ are equivalent if and only if $\frac{a}{b} = \frac{p}{q}$.

Usually, reducing a fraction means dividing both numerator and denominator by a common factor. But that is too hard, so little t proposes a new definition of reduction: we may simultaneously strike out several identical digits from the numerator and denominator at once. For example, $\frac{123}{233}$ can become $\frac{12}{23}$ by striking out one digit, or $\frac{13}{33}$; it is easy to see that this may make the original fraction no longer equivalent to the current one.

Now little t asks you: under this reduction operation, what is the simplest fraction of $\frac{a}{b}$? A simplest fraction is, among all $\frac{p}{q}$ equivalent to $\frac{a}{b}$, the one with the smallest $p$. For example:

• $\frac{163}{326} \rightarrow \frac{16}{26} \rightarrow \frac{1}{2}$, we say $\frac{1}{2}$ is the simplest fraction of $\frac{163}{326}$.
• The simplest fraction of $\frac{24}{48}$ is $\frac{24}{48}$, because $\frac{2}{8} \neq \frac{24}{48}$.
• The simplest fraction of $\frac{22222}{22222}$ is $\frac{2}{2}$, because $\frac{0}{0}$ is invalid.

Note that if the answer is $\frac{007}{233}$, you should output $\frac{7}{233}$. You can think of leading zeros as automatically vanishing during reduction.

Input Format

One line with two integers $a, b$, the numerator and denominator respectively.

Output Format

One line with two integers $p, q$, the numerator and denominator of the simplest fraction respectively.

Sample Input

2232 162936

Sample Output

232 16936

Constraints

For all data, $1 \le a, b \le 2^{63} - 1$.