HG - HUGE GCD

RK 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 professor provided him with N smaller integers whose product is A, and M integers with product B.

RK 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.

Input

The 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 10^9, 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 10^9, whose product is the number B.

Output

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.

Example

Input:
3
2 3 5
2
4 5

Output:
10
Input:
3
358572 83391967 82
3
50229961 1091444 8863

Output:
000012028

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


Added by:BLANKRK
Date:2014-01-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-02-22 09:30:08 Jumpy
how they did it in 0.00 sec, cannot get that mine taking .33 sec...
2014-02-16 17:36:30 NISHANT RAJ
AC in first go!!!!
2014-02-14 07:44:42 J.A.R.V.I.S.
@mjh use sys.stdin
2014-02-10 14:26:39 mjh
how to end input while using python
2014-02-10 05:27:28 I know nothing
easy if u know the basic of gcd
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.