Fraction Challenge

Time limit0.5sMemory limit512 MB

Summary
Multiply many huge fractions given as digit strings and output the reduced product as a/b.
Level

Hard8 of 10

Topics
String, Hash map, Number theory, Math
Solved
No attempts yet

Problem

When people are asked what their favorite number is, they usually answer with a natural number. Kipa also talks about natural numbers most of the time, but in fact Kipa loves fractions a lot too.

Multiplying all of Kipa's favorite fractions together produces the fraction Kipa really loves. Kipa is going to memorize this fraction, so Kipa worried that the numerator or denominator might get too long. Whether by luck or by wit, when that product is written as a reduced fraction, both the numerator and the denominator do not exceed 10910^9.

Let us make the fraction Kipa really loves and make Kipa happy.

Input

The first line gives nn, the number of fractions Kipa likes.

Lines 2 through n+1n+1 give Kipa's favorite fractions. Each line contains exactly one /. No line begins or ends with /, and every character in the line other than the / is a digit. The fraction represented by a line is a/ba/b, where aa is the decimal number to the left of the / and bb is the decimal number to the right. The first digit of each line and the digit right after the / are guaranteed not to be 0, and every prime factor of aa and bb is guaranteed not to exceed 10910^9.

The total number of digits across the nn lines starting from the second line does not exceed 2,000,000.

Output

On the first line, print the fraction Kipa really loves in the form a/b. It must be printed as a reduced fraction, and the numerator and denominator of the answer are guaranteed to be at most 10910^9.

Examples1

  1. Example 1

    Input
    5
    12/4
    3/18
    3/23
    5/22
    10/27
    
    Expected output
    25/4554