prietenie6

Cerință

Se consideră un șir de $n$ numere naturale nenule.

Pentru un număr natural $x$, numim divizor prietenos al lui $x$ orice divizor pozitiv $d$ al lui $x$ care îndeplinește simultan următoarele condiții:

1. suma cifrelor lui $d$ este un număr natural nenul;
2. această sumă divide pe $x$.

Indicele de prietenie al lui $x$ reprezintă numărul total de divizori prietenoși ai lui $x$.

Pentru fiecare dintre cele $n$ numere naturale date, se calculează indicele de prietenie. Cunoscând cerința $c$, $n$ numărul de numere și numerele din șir, se cere:

1. Să se determine valoarea din șir cu cel mai mare indice de prietenie. Dacă există mai multe valori cu același indice de prietenie maxim, se va afișa ultima dintre ele.
2. Să se afișeze, în ordine crescătoare, toate numerele din șir care au indicele de prietenie egal cu indicele de prietenie maxim găsit la punctul $1$.

Date de intrare

Fișierul de intrare prietenie.in conține pe prima linie numărul natural $c$ al cerinței, care poate fi doar $1$ sau $2$, pe a doua linie numărul natural nenul $n$ și apoi $n$ numere naturale nenule, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire prietenie.out va conține pe o linie valorile corespunzătoare cerinței (la cerința 2 numerele sunt separate prin câte un spațiu).

Restricții și precizări

• $2 \leq n \leq 100 \ 000$;
• Fiecare număr din șir este un număr natural nenul $\leq 100 \ 000$.
• Se garantează că există cel puțin un număr în șir.
• Pentru cerința $1$, se acordă $32$ de puncte.
• Pentru cerința $2$, se acordă $68$ de puncte.

Exemplul 1

prietenie.in

1
5
56 36 42 30 48

prietenie.out

48

Explicație

Şirul conține $5$ numere: $56$, $36$, $42$, $30$, $48$. Indicii de prietenie sunt: $56→5$, $36→9$, $42→7$, $30→8$, $48→9$.

Cerința este $1$, indicele de prietenie maxim este $9$, ultima valoare cu indicele de prietenie $9$ este $48$.

Exemplul 2

prietenie.in

2
5
56 36 42 30 48

prietenie.out

36 48

Explicație

Şirul conține $5$ numere: $56$, $36$, $42$, $30$, $48$. Indicii de prietenie sunt: $56→5$, $36→9$, $42→7$, $30→8$, $48→9$.

Cerința este $2$, indicele maxim de prietenie este $9$, iar valorile care au acest indice sunt (în ordine crescătoare): $36$ și $48$.