Shine on You Crazy Diamond

Limits 1s, 512 MB

This problem is authored by one of our late friends, Sifat, who unexpectedly left us last year. He was a brilliant programmer, an astute philosopher and an amazing human being. Had he been with us, he would have been delighted to see this year’s brilliant IUPC coming to life and would wish you good luck for the contest. We sincerely hope you enjoy his problem.

You are given an array $a$ of size $n$ . You can select a number $x > 1$ ( $x$ may or may not be an element of $a$ ) and remove every multiple of $x$ from the array. You need to find the minimum size of the array $a$ after performing this operation exactly twice.

Input

The first line contains an integer, $n (1 \leq n \leq 10^5)$ .

The second line contains $n$ space-separated integers $a_1, a_2, \cdots, a_n (1 \leq a_i \leq 10^6)$ .

Output

On the first line, output a single integer, the minimum size of array $a$ after performing this operation exactly twice.

On the second line, output two integers $x_1$ and $x_2$ $(2 \leq x_1, x_2 \leq 2^{31}-1)$ , the chosen values of $x$ for the two operations.

Samples

Input	Output
4 4 8 25 21	1 4 21
You can chose 4 and remove 4 8 to get the new array 25 21. Then you can chose 25 to get the new array 21 . So the answer is 1. There exists other choices that can give the same result too. For example 2 3 is a valid solution as well.

Input

Output

4
4 8 25 21

1
4 21

You can chose 4 and remove 4 8 to get the new array 25 21. Then you can chose 25 to get the new array 21 . So the answer is 1.

There exists other choices that can give the same result too. For example 2 3 is a valid solution as well.

Input	Output
3 2 4 6	0 2 1605113
If you choose 2 first, all elements are removed after the first move. Then you can choose any integer for the second move. As such 2 $x$ for any $2 \leq x \leq 2^{31}-1$ is a valid output.