12 1 s 128 MB

Seung-kyoo has received a homework assignment to compute the **greatest common divisor** of the two positive integers **A** and **B**.

Since the numbers are quite large, the teacher provided him with **N** smaller integers whose product is **A**, and **M** integers with product **B**.

Seung-kyoo would like to verify his result, so he has asked you to write a program to solve his problem. If the result is more than 9 digits long, output only the **last 9** digits.

The first line of input contains the positive integer **N** (1 ≤ **N** ≤ 1,000).

The second line of input contains **N** space-separated positive integers less than 1,000,000,000, whose product is the number **A**.

The third line of input contains the positive integer **M** (1 ≤ **M** ≤ 1,000). The fourth line of input contains **M** space-separated positive integers less than 1,000,000,000, whose product is the number **B**.

The first and only line of output must contain the greatest common divisor of numbers **A** and **B**. If the result is more than 9 digits long, output only the last (least significant) 9 digits.

## Sample Input | ## Sample Output |
---|---|

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

**First sample description: **The greatest common divisor of numbers A = 30 and B = 20 equals 10.