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 spaceseparated 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 spaceseparated 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
rising_stark:
20200727 17:03:57
Just because of those leading zeros, I had to write a code of worse time complexity.


rising_stark:
20200727 15:35:34
can someone explain the output format here?


purplecs:
20191118 18:57:18
used BigInteger in java 

improve:
20181211 08:54:53
take care of the preceding zeroes. 

eagleshadow:
20181004 21:36:28
my 50th xD


divyansh_soni:
20180806 18:23:21
AC in one go... 

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

sagnik_66:
20170528 10:15:00
BigInteger makes it so easy! Don't forget to observe the output condition!! 

kira28:
20161209 21:43:35
INTEGER in JAVA !!!


akshayvenkat:
20161119 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. 
Added by:  BLANKRK 
Date:  20140128 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 