레이팅 미적용Mirko 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\).
Mirko 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 \le N \le 1000\)).
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 \le M \le 1000\)).
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.
Note: In the third sample, the result has more than \(9\) digits, so only the last \(9\) digits (with leading zeros) are printed.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Test 1 | 10점 | None |
Test 2 | 10점 | None |
Test 3 | 10점 | None |
Test 4 | 10점 | None |
Test 5 | 10점 | None |
Test 6 | 10점 | None |
Test 7 | 10점 | None |
Test 8 | 10점 | None |
Test 9 | 10점 | None |
Test 10 | 10점 | None |
3
2 3 5
2
4 5104
6 2 3 4
1
113
358572 83391967 82
3
50229961 1091444 8863000012028