comun

Tocmai ai primit un şir $v$ de $K$ numere naturale nenule distincte. Plecând de la acest şir, te-ai gândit să construieşti un şir $w$ de $N$ numere naturale distincte, astfel încât un număr $x$ este în şirul $w$ dacă şi numai dacă exista iniţial în şirul $v$ sau se pot alege cel puţin două numere din şirul $v$ astfel încât $x$ este cel mai mare divizor comun al acelor numere.

De exemplu, dacă $v = [4, 6, 7]$ atunci $w = [1, 2, 4, 6, 7]$.

Uimit de proprietăţile matematice frumoase ale noului şir $w$, ai uitat din păcate şirul original $v$ de la care ai pornit.

Cerință

Dându-se şirul $w$, să se găsească un şir posibil iniţial $v$ având un număr minim de elemente.

Date de intrare

Fişierul de intrare comun.in conţine pe prima linie un număr natural $N$. Pe cea de-a doua linie se află $N$ numere naturale nenule distincte, în ordine strict crescătoare, reprezentând şirul $w$.

Date de ieșire

Fişierul de ieşire comun.out va conţine pe prima linie numărul minim $K$ de elemente ale şirului $v$. Pe cea de-a doua linie se vor afla $K$ numere naturale distincte, în ordine strict crescătoare, reprezentând şirul propriu-zis.

Restricții și precizări

• Toate valorile din fişierul de intrare sunt numere naturale nenule mai mici sau egale cu $100 \ 000$.
• Pentru teste în valoare de 15 puncte, toate valorile din fişierul de intrare sunt mai mici sau egale cu $20$.
• Pentru teste în valoare de 50 de puncte, toate valorile din fişierul de intrare sunt mai mici sau egale cu $2 \ 000$.
• Se garantează că există măcar o soluţie.
• Dacă există mai multe şiruri iniţiale cu număr minim de elemente, oricare este acceptat.

Exemplul 1

comun.in

5
1 2 4 6 7

comun.out

3
4 6 7

Explicație

$1 = \text{cmmdc}(6, 7) = \text{cmmdc}(4, 6, 7)$
$2 = \text{cmmdc}(4, 6)$
Se poate demonstra că orice alt şir cu proprietatea cerută are măcar $3$ elemente.

Exemplul 2

comun.in

4
2 4 8 16

comun.out

4
2 4 8 16

Explicație

Nu există niciun şir de mai puţin de $4$ elemente cu proprietatea cerută.