Greatest Common Divisor

Time limit1sMemory limit192 MB

Summary
Given two lists of up to 1000 factors whose products form huge numbers A and B, compute gcd(A,B) modulo the last 9 digits using prime factorization instead of big integers.
Level

Medium6 of 10

Topics
Number theory, Math, Hash map
Solved
No attempts yet

Problem

There are two positive integers A and B. A is the product of N given positive integers, and B is the product of M given positive integers. These products may be very large.

Given both lists of factors, compute the greatest common divisor of A and B.

Input

The first line contains N (1 <= N <= 1000). The second line contains N positive integers separated by spaces. Each integer is less than 1,000,000,000, and their product is A.

The third line contains M (1 <= M <= 1000). The fourth line contains M positive integers separated by spaces. Each integer is less than 1,000,000,000, and their product is B.

Output

Print the greatest common divisor of A and B. If its decimal representation has more than 9 digits, print only the last 9 digits. If those final 9 digits start with zeroes, print those zeroes too.

Examples3

  1. Example 1

    Input
    3
2 3 5
2
4 5
    Expected output
    10

  2. Example 2

    Input
    4
6 2 3 4
1
1
    Expected output
    1

  3. Example 3

    Input
    3
358572 83391967 82
3
50229961 1091444 8863
    Expected output
    000012028