P10383 "HOI R1" Fraction Reduction Selection

**Please note the unusual time limit of this problem.** Because Python comes with built-in high-precision multiplication and runs fairly fast, brute-force programs written in Python can pass most test points under normal time limits. Therefore, the time limit for this problem is set to $200\text{ms}$. *** Mr. Huang is a math teacher who is very good at calculations and is famous for "Huang-style reduction." Now he asked little $\iiint$ to solve this problem. But little $\iiint$ **seems** not very capable, so he asks you for help.

Represent $$\dfrac{\displaystyle\prod_{i=1}^n a_i}{\displaystyle\prod_{j=1}^m b_j}$$ as a *lowest-term fraction $^{[1]}$* $\dfrac{p}{q}$, and output $p$ and $q$. A kind classmate also gave little $\iiint$ an integer $C$, which is the Subtask that the test point belongs to.

The first line contains three integers $n$, $m$, and $C$. The second line contains $n$ integers $a_{1\dots n}$. The third line contains $m$ integers $b_{1\dots m}$.

Output two numbers $p$ and $q$ in the first line.

**Notes** $[1]$：[Baidu Baike](https://baike.baidu.com/item/%E6%9C%80%E7%AE%80%E5%88%86%E6%95%B0/2821376?fr=ge_ala)：A lowest-term fraction is a fraction whose numerator and denominator have only the common factor $1$. In other words, the numerator and denominator are coprime. It is also called a reduced fraction. For example: one half, two thirds, nine eighths, three eighths, and so on. *** **Sample Explanation** $\dfrac{540000\times350000\times110000\times130000\times170000\times970000}{2000\times5000\times1000\times1000\times97000\times17000\times143000\times210000}=\dfrac{9}{10}$, $\gcd(9,10)=1$. *** **Constraints and Agreements** **This problem uses bundled tests.** |Subtask|Score|Constraints| |-|-|-| |#0|0|Same as the sample| |#1|$5$|$1\le n,m\le500$, $1\le a_i,b_i\le9\times10^{18}$, $1\le p,q\le3\times10^9$| |#2|$5$|$1\le n,m\le25000$, $1\le a_i,b_i\le9\times10^{18}$, $1\le p,q\le10$| |#3|$10$|$1\le n,m\le5000$, $1\le a_i,b_i\le3\times10^9$, $1\le p,q\le3\times10^9$| |#4|$15$|$1\le n,m\le10000$, $1\le a_i,b_i\le9\times10^{18}$, $1\le p,q\le3\times10^9$| |#5|$20$|$1\le n,m\le25000$, $1\le a_i,b_i\le9\times10^{18}$, $1\le p\le3\times10^9$, $q=1$| |#6|$10$|$1\le n,m\le25000$, $1\le a_i,b_i\le9\times10^{18}$, $1\le p\le3\times10^9$, $1\le q \le25000$| |#7|$20$|$1\le n,m\le25000$, $1\le a_i,b_i\le9\times10^{18}$, $1\le p,q\le3\times10^9$| |#8|$10$|$1\le n,m\le10^6$, $1\le a_i,b_i\le10^6$, $1\le p,q\le3\times10^9$| |#9|$5$|$1\le n,m\le10^6$, $1\le a_i,b_i\le9\times10^{18}$, $1\le p,q\le3\times10^9$| *** **Tips** ~~Nobody writes high precision.~~ The time limit is small and the input size is large. If you believe your algorithm has the right complexity, try optimizing your I/O speed. Translated by ChatGPT 5