문제2010--Homework

2010: Homework

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 72  통과: 16
[제출] [채점기록] [묻고답하기]

문제 설명

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.

입력 예시 Copy

3
2 3 5
2
4 5

출력 예시 Copy

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

Hint

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

출처/분류