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.

riseoj 작성

출처 COCI 2011/2012 Contest 2