题目描述

给定 $N$ 个正整数 $A_1,A_2,...,A_N$ 和 $M$ 个正整数 $B_1,B_2,...,B_M$，求：

$$\gcd(\prod\limits_{i=1}^NA_i,\prod\limits_{i=1}^MB_i) $$

输入格式

第一行包含一个正整数 $N$。

第二行包含 $N$ 个正整数 $A_i$。

第三行包含一个正整数 $M$。

第四行包含 $M$ 个正整数 $B_i$。

输出格式

输出一行，表示答案。如果答案超过九位数，你只需输出它的最后九位即可。

3
2 3 5
2
4 5

10

4
6 2 3 4
1
1

1

3
358572 83391967 82
3
50229961 1091444 8863

000012028

提示

【样例 1 解释】

$\gcd(30,20) = 10$，因此答案为 $10$。

【数据范围】

对于 $100\%$ 的数据，$1 \le N,M \le 1000$，$1 \le A_i,B_i \le 10^9$。

【说明】

本题分值按 COCI 原题设置，满分 $100$。

题目译自 COCI2011-2012 CONTEST #2 T3 ZADAĆA。