背景

请注意本题并不寻常的时间限制。

由于 python 自带对于高精度乘法的实现，并且运行效率较高，导致其编写的暴力程序，在一般的时间限制下可以通过绝大部分点。故本题时限开到 $200\text{ms}$。

---

黄总是一名计算很强的数学老师，以黄氏约分而闻名。现在他请小 $\iiint$ A 了这道题。但小 $\iiint$ 似乎有点菜，所以求助于你。

题目描述

把

$$\dfrac{\displaystyle\prod_{i=1}^n a_i}{\displaystyle\prod_{j=1}^m b_j}$$

表示为最简分数 $^{[1]}$ $\dfrac{p}{q}$，求 $p$ 和 $q$。

好心的同学还给了小 $\iiint$ 一个整数 $C$，即数据点所在的 Subtask。

输入格式

第一行三个整数 $n,m$ 和 $C$。

第二行 $n$ 个整数 $a_{1\dots n}$。

第三行 $m$ 个整数 $b_{1\dots m}$。

输出格式

第一行两个数 $p$ 和 $q$。

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

9 10

提示

注释

$[1]$：百度百科：最简分数，是分子、分母只有公因数 $1$ 的分数，或者说分子和分母互质的分数，又称既约分数。如：二分之一，三分之二，九分之八，八分之三等等。

---

样例解释

$\dfrac{540000\times350000\times110000\times130000\times170000\times970000}{2000\times5000\times1000\times1000\times97000\times17000\times143000\times210000}=\dfrac{9}{10}$，$\gcd(9,10)=1$

---

数据规模与约定

本题采用捆绑测试。

Subtask	分值	数据范围
#0	0	同样例
#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$

---

提示

高精度狗都不写。

本题时限较小且输入量较大，若你认为自己的算法复杂度正确，请尝试优化读写速度。