题目描述

Mirko 刚学会了如何求两个整数 A 和 B 的最大公约数。由于 A 和 B 都非常大，所以我们不能直接给出，我们知道 A 是由 N 个正整数相乘得到的，我们也知道 B 是由 M 个正整数相乘得到的。你的任务就是求 A 和 B 的最大公约数。如果最大公约数超过 9 位，那么你只需要结果的后 9 位即可。

输入格式

第一行，一个整数 N 。( 1 ≤ N ≤ 1000 )。

第二行，N 个正整数，这 N 个整数的乘积就等于 A 。每个正整数的范围：[1，1000000000]。

第三行，一个整数 M 。( 1 ≤ M ≤ 1000 )。

第四行，M个正整数，这 M 个整数的乘积就等于 B 。每个正整数的范围：[1，1000000000]。

输出格式

A 和 B 的最大公约数。如果超过 9 位，输出后 9 位数字。

样例

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