C. Cavern of Runes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yuri Alberto, the people's favorite and Corinthians' star number 9, will be in Curitiba on August 27 to face Athletico Paranaense in the quarterfinals of the Copa do Brasil. Obviously, his victory is already a sure thing because there's no way a small team like CAP can beat the biggest team in the world!

Therefore, Yuri and his adventurous spirit have already planned to take a tour of the state of Paraná after his victory. He is truly worthy of the title of protagonist, as in addition to playing very well, he also dominates a great deal of knowledge about archaeology and rock runes. Because of this, the tour he chose to take was to enter a cave filled with enigmatic runes dating back more than 4000 years, with a legend of a cursed treasure waiting for some star of knowledge to rescue it.

Upon entering the cave, Yuri discovered that the runes are organized into $$$N$$$ panels, each containing a sequence of ancient numbers. A legend carved on the wall reveals:

To unlock the secret of the cursed treasure, the seeker must first purify each panel, maximizing the common essence of each sequence. The seeker may remove one of the runes from the sequence if desired to maximize the common essence of a sequence. Once the panels are purified, gather all the essences obtained. The destination of the treasure will be the smallest possible harmonious multiple of the gathered essences, and it is possible to remove one of the essences (if more than one exists) to minimize the harmonious multiple.

The common essence of a set is defined as the largest number that is a factor of all numbers, better known as the greatest common divisor (GCD). The harmonious multiple of a set is defined as the smallest integer that is a multiple of all elements of the set, better known as the least common multiple (LCM).

Yuri Alberto, with his expertise, knows that the solution to this puzzle requires precision and efficiency, as the runes can be numerous and the treasure will not wait. He has asked for your help in developing a program that will find the value of the cave's puzzle.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^{5}$$$), the number of panels. This is followed by $$$N$$$ lines, each representing a panel. For each panel, an integer $$$A$$$ ($$$2 \leq A \leq 10^{5}$$$) is first given, representing the number of runes on that panel, followed by $$$A$$$ positive integers $$$v_j$$$ ($$$1 \leq v_j \leq 42$$$), representing the values of the runes. The sum of all $$$A$$$ does not exceed $$$2 \times 10^{5}$$$.

Output

A single integer, the value of the cave riddle after following the ritual described. It is guaranteed that this value does not exceed $$$10^{18}$$$.

Examples
Input
3
3 12 24 30
2 8 6
3 4 6 8
Output
8
Input
4
4 32 35 42 15
2 35 40
2 24 12
3 24 11 7
Output
24
Note

Explanation for example 1

  • In the first panel $$$[12,24,30]$$$: removing $$$30$$$ results in $$$\mathrm{GCD}(12,24) = 12$$$, which is the largest possible value.
  • In the second panel $$$[8,6]$$$: removing $$$6$$$ results in $$$\mathrm{GCD}(8) = 8$$$, which is the largest possible value.
  • In the third panel $$$[4,6,8]$$$: removing $$$6$$$ results in $$$\mathrm{GCD}(4,8) = 4$$$, which is the largest possible value.

Collecting the essences: $$$[12,8,4]$$$. Removing $$$12$$$, we have $$$\mathrm{LCM}(8,4) = 8$$$, which is the smallest possible value. Therefore, the final result is $$$8$$$.