Time Limit: 2s Memory Limit: 256MB

题目描述

有两个很大的数,由于这两个数实在是有点大,所以这两个数均以若干个较小数的乘积的形式给出。
现在请你计算这两个数的最大公因数和最小公倍数。由于这个结果可能很大,因此你只需要输出答案对 1e9+7 取模的结果。

输入格式

第一行是一个整数 \(T\;(1 <= T <= 400)\),表示数据组数。
对于每一组数据:
第一行包括两个正整数 \(n, m(1<=n, m<=100000) \),分别表示这两个大数的因子个数。
第二行包括 \(n\) 个大于 1 的整数\(a_1,a_2,…,a_n, 1 < a_i < 1000\),表示组成第一个大数的因子。
第三行包括 \(m\) 个大于 1 的整数\(b_1,b_2,…,b_m, 1 < b_i < 1000\),表示组成第二个大数的因子。

数据保证 \(n\) 的总和与 \(m\) 的总和均不超过 1000000。

输出格式

对于每组测试用例用一行输出两个数,第一个数表示这两个大数的最大公因数,第二个数表示这两个大数的最小公倍数,答案对 1e9+7 取模。

样例输入

1
2 2
30 2 
20 2

样例输出

20 120

样例解释

第一个数是 \(30*2=60\),第二个数是 \(20*2=40\),显然有 \(gcd(60, 40) = 20\),\(lcm(60, 40) = 120\),它们对 1e9+7 取模后值不变。