Rational Ratio

Interview

Time limit2sMemory limit512 MB

Summary

Convert a decimal with a repeating rightmost digit block into a fully reduced fraction formed by integer subtraction.

Level: Medium4 of 10
Topics: Math, Number theory, String, Implementation
Solved: No attempts yet

Problem

Every positive rational number can be expressed as a ratio of two positive integers. In decimal form, however, rational numbers often have an infinitely repeating pattern, for example $1/7 = 0.142857142857142857\ldots$ . A convenient way of writing this repeating pattern is to put a bar over the first occurrence of the repeating part, so $1/7$ would be written as

$0.\overline{142857}$

Given a rational number consisting of a series of digits, a decimal point, more digits, and then a number indicating how many of the rightmost digits repeat (that is, the number of digits under the bar), find the ratio of two integers, in the most reduced form, that represents the same rational number. For example, for the input "0.142857 6" you should find $1/7$ .

Input

The input is a single line with two numbers separated by one space. The first number consists of 1 to 3 digits (0-9), a decimal point, and 1 to 11 digits (0-9), representing the decimal form of the number, possibly with leading zeros. The second number is a positive integer indicating how many of the rightmost digits of the preceding number repeat. The first number is always greater than 0. The second number is never less than 1 nor larger than the number of digits to the right of the decimal point.

Output

Print the corresponding fraction in its most reduced form, that is, the fraction with the smallest possible integer values in the numerator and denominator.

Examples3

Example 1
Input
```
0.142857 6
```
Expected output
```
1/7
```
Example 2
Input
```
1.6 1
```
Expected output
```
5/3
```
Example 3
Input
```
123.456 2
```
Expected output
```
61111/495
```