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.


hide comments
sandeep_4141: 2017-06-09 10:27:32

In c++ ,use your logic with long int and you should use printf ,scanf instead of cin,cout >>:)

sagnik_66: 2017-05-28 10:15:00

BigInteger makes it so easy! Don't forget to observe the output condition!!

kira28: 2016-12-09 21:43:35

INTEGER in JAVA !!!
finally AC

akshayvenkat: 2016-11-19 23:06:22

Stupid question, since the '0's are to be printed unnecessarily. The answer MODULO 10^9+7 is a much better and convenient alternative. So many changes had to be done to my code for such a trivial demand.

Madhukar Reddy: 2016-09-11 07:57:31

I am getting NZEC error, could you please help me with this. http://ideone.com/cD9irG

mohitgupta07: 2016-05-11 01:10:22

getting wrong answer -_- -_- using biginteger too nd still :/ someone hint or help plz

Diksha Jaiswal: 2015-09-26 09:55:20

AC in one attempt :D :D

:.Mohib.:: 2015-05-26 10:51:20

Done in python......Best python solution..... :)

Last edit: 2015-05-26 11:06:54
Rahul Jain: 2014-09-24 12:19:36

Will O(m*n) be sufficient or do I need more efficient code?

P_Quantum: 2014-05-18 21:00:26

AC in first go :P


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