Interesant

Se consideră o mulțime $S$ care conține $N$ șiruri de caractere formate din litere mici ale alfabetului englezesc.

Un șir de caractere se numește interesant în raport cu celelalte șiruri ale mulțimii, dacă nu există un alt șir în mulțime care să-l conțină ca subșir. De exemplu, dacă mulțimea $S$ conține șirurile abc, bde și abcdef, atunci singurul șir interesant este abcdef deoarece abc și bde nu îl conțin ca subșir. Mai mult, abc și bde sunt subșiruri în abcdef, deci nu sunt interesante.

Cerințe

Fiind dată o mulțime $S$ formată din $N$ șiruri de caractere se cere:

1. Să se determine cel mai lung șir. Dacă sunt mai multe șiruri având aceeași lungime maximă, se cere cel mai mic din punct de vedere lexicografic.
2. Să se determine toate șirurile interesante din mulțimea $S$.

Date de intrare

Fișierul de intrare interesant.in conține pe prima linie două numere naturale $p$ și $N$, despărțite prin spațiu. Pentru toate testele de intrare, numărul $p$ poate avea doar valoarea $1$ sau valoarea $2$. Pe următoarele $N$ linii, se găsesc șirurile de caractere, câte unul pe linie.

Date de ieșire

Dacă valoarea lui $p$ este $1$, se va rezolva numai cerința $1$.

În acest caz, în fișierul de ieșire interesant.out se va scrie cel mai lung șir dintre cele citite. Dacă există mai multe șiruri de aceeași lungime, se va scrie cel mai mic din punct de vedere lexicografic.

Dacă valoarea lui $p$ este $2$, se va rezolva numai cerința $2$.

În acest caz, fișierul de ieșire interesant.out va conține pe prima linie o valoare $K$ ce reprezintă numărul de șiruri interesante, iar pe următoarele $K$ linii, șirurile interesante în ordinea în care apar în fișierul de intrare.

Restricții și precizări

• $2 \leq N \leq 200$
• Lungimea unui șir va fi cuprinsă între $1$ și $5 \ 000$.
• Un subșir al șirului de caractere $C_0 C_1 C_2 \dots C_k$ se definește ca fiind o succesiune de caractere $C_{i_1} C_{i_2} C_{i_3} \dots C_{i_k}$, unde $0 \leq i_1 < i_2 < i_3 < \dots < i_k \leq k$.
• Fișierul de intrare NU conține șiruri identice.

Exemplul 1

interesant.in

1 5
abcacaaz
ad
abcacaad
acd
zyt

interesant.out

abcacaad

Explicație

$p=1$

Fișierul de intrare conține $5$ șiruri.

abcacaad este șirul de lungime maximă. Șirul abcacaaz are aceeași lungime, dar este mai mare din punct de vedere lexicografic.

Atenție! Pentru acest test se rezolvă doar cerința 1.

Exemplul 2

interesant.in

2 5
abcacaad
ad
zayyt
acd
zyt

interesant.out

2
abcacaad
zayyt

Explicație

$p=2$

ad, acd sunt subșiruri al lui abcacaad, iar zyt este subșir al lui zayyt.

Atenție! Pentru acest test se rezolvă doar cerința 2.