We call an integer a prime number (or simply a prime) if its only positive divisors are and .
Fundamental theorem of arithmetic states: Every positive integer can be uniquely expressed as a product of power of primes, i.e.,
where,
- is the prime, i.e.,
Greatest common divisor of two positive integers
For two positive integers, and , whose prime factorization is represented as
We calculate the greatest common divisor, , as
Greater common divisor of a list of numbers
Greatest common factor of a list of positive integers, , is represented as
Finite representation of prime factorization
Since primes are infinite, it is not possible to store factors in the form provided above. To that end, we will only consider those prime factors () whose power is greater than zero (). That is:
, where
- ; for rest
And we will represent them as following:
For example:
Challenge
You are given the elements of list, , in the representation provided above. Find its greatest common divisor, i.e., .
Input Format
First line contains an integer, , which is the size of list, .
Then follows lines, where line represents the factors of element of ,
Output Format
Print one line representing the greatest common divisor of () in the above representation.
Constraints
- All other integers lie in
- Total number of prime factors of an element
Notes
- Test cases are designed such that will always be greater than .
Sample Input #00
2
7 2
2 2 7 1
Sample Output #00
7 1
Sample Input #01
4
2 2 3 2 5 3
3 2 5 3 11 1
2 2 3 3 5 4 7 6 19 18
3 10 5 15
Sample Output #01
3 2 5 3
Explanation
Test case #00: . Therefore .
Test case #01: .