eolymp
bolt
Try our new interface for solving problems
Problems

Big Division

Big Division

A theoretical physicist friend is doing research about the "Answer to the Ultimate Question of Life, the Universe, and Everything", he thinks that it is not \textbf{42} as suggested by "The Hitchhiker's Guide to the Galaxy" science fiction comedy series; instead he thinks it is the result of dividing the products of two sequences of positive integers \textbf{A} and \textbf{B}! The task of calculating the product of \textbf{A} and \textbf{B} followed by division turned out to be not as easy as it looks, specially with the sequences being long and the products getting too large very quickly! Even using a modern computer, a straight forward implementation for the calculations may take very long time to complete! And this is where we seek your help as a brilliant computer scientist! \InputFile The first line of input contains an integer (\textbf{1} ≤ \textbf{T} ≤ \textbf{200}), the number of test cases. \textbf{T} test cases follow, the first line of each test case contains two integers (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{110,000}), the lengths of sequences \textbf{A} and \textbf{B} respectively. Two lines follow, the first line contains \textbf{N} space separated integers (\textbf{0} < \textbf{A_0}, \textbf{A_1} … \textbf{A_n} ≤ \textbf{1,000,000}), and the second line contains \textbf{M} space separated integers (\textbf{0} < \textbf{B_0}, \textbf{B_1} … \textbf{B_m} ≤ \textbf{1,000,000}). \OutputFile For each test case, print one line containing the result of dividing the product of sequence \textbf{A} by the product of sequence \textbf{B} as a reduced fraction of the format "\textbf{X / Y}" (Notice the single space before and after the fraction sign). \textbf{X} and \textbf{Y} are guaranteed to fit in \textbf{32}-bit signed integer. A reduced fraction is a fraction such that the greatest common divisor between the nominator and the denominator is \textbf{1}.
Time limit 1 second
Memory limit 64 MiB
Input example #1
2
3 1
2 4 5
12
2 4
1 15
5 1 7 2
Output example #1
Case #1: 10 / 3
Case #2: 3 / 14
Source The Third Lebanese Collegiate Programming Contest