「HOI R1」杂分选约

**请注意本题并不寻常的时间限制。** 由于 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]$：[百度百科](https://baike.baidu.com/item/%E6%9C%80%E7%AE%80%E5%88%86%E6%95%B0/2821376?fr=ge_ala)：最简分数，是分子、分母只有公因数 $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|$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$| *** **提示** ~~高精度狗都不写。~~ 本题时限较小且输入量较大，若你认为自己的算法复杂度正确，请尝试优化读写速度。