Big Division#2729
A theoretical physicist friend is conducting research on the "Answer to the Ultimate Question of Life, the Universe, and Everything." He believes it is not , as suggested by the science fiction comedy series "The Hitchhiker's Guide to the Galaxy." Instead, he thinks it is the result of dividing the products of two sequences of positive integers and !
The task of calculating the product of and followed by division is not as easy as it appears, especially when the sequences are long and the products grow very large very quickly! Even with a modern computer, a straightforward approach to these calculations may take too long to complete. This is why we need your help as a brilliant computer scientist!
The first line of input contains an integer 1 \leq T \leq 200, the number of test cases. Each test case follows. The first line of each test case contains two integers 1 \leq N, M \leq 110\,000, the lengths of sequences and , respectively. Two lines follow: the first line contains space-separated integers (0 < A_0, A_1, \ldots, A_{N-1} \leq 1\,000\,000), and the second line contains space-separated integers (0 < B_0, B_1, \ldots, B_{M-1} \leq 1\,000\,000).
For each test case, print one line containing the result of dividing the product of sequence by the product of sequence as a reduced fraction in the format "" (note the single space before and after the fraction slash). and are guaranteed to fit in a -bit signed integer. A reduced fraction is a fraction such that the greatest common divisor between the numerator and the denominator is .
Example 1