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
2024-08-28 19:12:57
is o(n*M) enough?in c++
2024-04-29 21:30:06 Adamos Ttofari
it's incredibly easy if you are using python.
it's not worth wasting time writing it in C++.
2020-07-27 17:03:57
Just because of those leading zeros, I had to write a code of worse time complexity.
You can't use binary exponentiation because the digits in the result are not calculated correctly that way.

Costed me 2 WA :(
2020-07-27 15:35:34
can someone explain the output format here?
In first test case, there is 10 without leading zeros.
In second test case there is 12028 with leading zeros.

When should I print leading zeros and when not?
2019-11-18 18:57:18
used BigInteger in java
2018-12-11 08:54:53
take care of the preceding zeroes.
2018-10-04 21:36:28
my 50th xD
AC in one GO

Last edit: 2018-10-04 21:40:05
2018-08-06 18:23:21
AC in one go...
2017-06-09 10:27:32
In c++ ,use your logic with long int and you should use printf ,scanf instead of cin,cout >>:)
2017-05-28 10:15:00
BigInteger makes it so easy! Don't forget to observe the output condition!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.