Background

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.

Problem Description

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.

Input Format

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 Format

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

6 8 0
540000 350000 110000 130000 170000 970000
2000 5000 1000 1000 97000 17000 143000 210000

9 10

Hint

Notes

$[1]$：Baidu Baike：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		$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