ZADACA - COCI
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.
InputThe first line of input contains the positive integer N (1 ≤ N ≤ 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 ≤ M ≤ 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 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 ≤ 1000). The fourth line of input contains M space-separated positive integers less than 1 000 000 000, whose product is the number B.
OutputThe 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.
Input:
3
2 3 5
2
4 5Output:
10Input:
4
6 2 3 4
1
1Output:
1Input:
3
358572 83391967 82
3
50229961 1091444 8863Output:
000012028Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.