Problem Description

Given \( N \) positive integers \( A_1, A_2, \ldots, A_N \) and \( M \) positive integers \( B_1, B_2, \ldots, B_M \), find:

\[ \gcd\left(\prod_{i=1}^N A_i, \prod_{i=1}^M B_i\right) \]

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 a single line representing the answer. If the answer exceeds nine digits, you only need to output its last nine digits.

Sample Input and Output

Sample Input #1

3
2 3 5
2
4 5

Sample Output #1

10

Sample Input #2

4
6 2 3 4
1
1

Sample Output #2

1

Sample Input #3

3
358572 83391967 82
3
50229961 1091444 8863

Sample Output #3

000012028

Notes

Sample 1 Explanation

\[ \gcd(30, 20) = 10 \]
Thus, the answer is \( 10 \).

Data Range

For \( 100\% \) of the data, \( 1 \le N, M \le 1000 \), \( 1 \le A_i, B_i \le 10^9 \).

Notes

This problem is scored according to the original COCI settings, with a full score of \( 100 \).

The problem is translated from COCI2011-2012 CONTEST #2 T3 ZADAĆA.

见题面 Input 部分

见题面 Output 部分