408758: GYM103295 F Civil War

Dr. Stronge has a lot of superhero friends, like the Hulc and Admiral USA, and he likes to keep tabs on all of their affairs (sometimes by looking into the future). Recently, Dr. Stronge has grown concerned about a brewing feud between the heroes, that could erupt into a full-blown civil war! But in order for a civil war to break out among the superheroes, there would need to be something powerful dividing them all...

To investigate this possibility, Dr. Stronge has sent a survey out to his $$$N$$$ superhero friends, asking each of them their favorite number $$$f_i$$$, and everyone responded. Dr. Stronge believes that a civil war is imminent if there exists some $$$d=a^p$$$ where integers $$$a, p \geq 2$$$ such that $$$d$$$ divides $$$f_i$$$ for all $$$i$$$. In other words, he wants to know whether each superhero's favorite number is divisible by a common divisor that is equal to some number taken to a higher power.

Help Dr. Stronge predict whether or not there will be a civil war! Given $$$N$$$ superhero favorite numbers, output the largest value of $$$d$$$ such that it divides all of the heroes' favorite numbers and is of the form $$$a^p$$$ for some $$$a, p \geq 2$$$, or output NO CIVIL WAR if there is no such divisor $$$d$$$.

The first line of input contains an integer $$$N$$$ ($$$1 \leq N \leq 10^3$$$) denoting the number of superheroes surveyed by Dr. Stronge. The next line contains $$$N$$$ space-separated integers $$$f_1$$$ through $$$f_N$$$ ($$$1 \leq f_i \leq 10^6$$$) which are the superheroes' favorite numbers.

On a single line, print the largest $$$d$$$ satisfying Dr. Stronge's civil war requirement, or NO CIVIL WAR if none exists.

6
27 72 45 99 126 54

9

3
100 6 14

NO CIVIL WAR