Description

Given $N$ positive integers $A_1, A_2, ..., A_N$ and $M$ positive integers $B_1, B_2, ..., B_M$, compute:

$$\gcd(\prod\limits_{i=1}^N A_i, \prod\limits_{i=1}^M B_i)$$

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ positive integers $A_i$.

The third line contains a positive integer $M$.

The fourth line contains $M$ positive integers $B_i$.

Output Format

Output one line containing the answer. If the answer has more than nine digits, you only need to output its last nine digits.

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

Hint

Sample 1 Explanation

$\gcd(30, 20) = 10$, so the answer is $10$.

Constraints

For $100\%$ of the testdata, $1 \le N, M \le 1000$, and $1 \le A_i, B_i \le 10^9$.

Notes

The scoring of this problem follows the original COCI problem settings, with a full score of $100$.

This problem is translated from COCI2011-2012 CONTEST #2 T3 ZADAĆA。

Translated by ChatGPT 5