Mun

La o conferință MUN (Model United Nations) participă $N$ delegați din întreaga lume. Fiecare delegat primește un cod format din cel puțin una și cel mult $10$ litere mari distincte ale alfabetului englez. Delegații din aceeași țară au codul format din exact aceleași litere, eventual dispuse în altă ordine. Codurile a doi delegați din țări distincte diferă prin cel puțin o literă care apare în unul, dar nu și în celălalt. Numărul de delegați din țara gazdă este cel puțin jumătate plus unu din numărul total de delegați care participă la conferință și sunt cel puțin două țări reprezentate la conferință. La acest gen de conferință există o masă rotundă. Delegații care vor lua loc la masa rotundă sunt cei care dezbat (numiți vorbitori), iar toți ceilalți vor primi statut de supervizori. Rolul fiecărui delegat precum și numărul de delegați care iau loc la masa rotundă nu sunt prestabilite, dar protocolul prevede că la această masă nu pot sta doi delegați din aceeași țară în poziții alăturate (la stânga sau la dreapta)

Cerință

1. Să se determine $D$, numărul delegațiilor, adică numărul de țări reprezentate la conferință de cel puțin un delegat.
2. Să se determine două numere naturale, $S$ și $V$, $S$ reprezentând numărul minim de delegați care pot primi statut de supervizor, iar $V$ numărul de vorbitori corespunzător numărului $S$ determinat.
3. Să se afișeze codurile corespunzătoare numărului maxim de vorbitori ce pot sta la masa rotundă, în ordinea așezării la masă, începând de la oricare dintre ei, astfel încât dacă sunt mai multe posibilități de aranjare se va afișa cea mai mică din punctul de vedere lexicografic.

Date de intrare

Pe prima linie a fişierului de intrare mun.in este scris un număr natural $c$, reprezentând cerința ($1, 2$ sau $3$).

Pe linia a doua a fișierului este scris un număr natural $N$, reprezentând numărul delegaților participanți la conferință, iar pe a treia linie sunt scrise $N$ cuvinte formate din cel puțin una și cel mult $10$ litere mari ale alfabetului englez, reprezentând codurile acestor delegați. Cuvintele sunt separate prin câte un spațiu.

Date de ieșire

Dacă $c = 1$, pe prima linie a fișierului de ieșire mun.out va fi scris un număr natural $D$, cu semnificația din enunț.

Dacă $c = 2$, pe prima linie a fișierului de ieșire mun.out vor fi scrise două numere naturale $S$ și $V$, separate printr-un spațiu, cu semnificația din enunț.

Dacă $c = 3$, pe prima linie a fișierului de ieșire mun.out va fi scris șirul de cuvinte, separate prin câte un spațiu, reprezentând codurile vorbitorilor care stau la masa rotundă, conform cerinței $3$.

Restricții și precizări

• $5 \leq N \leq 10 \ 000$
• Spunem că șirul $x_1, x_2 \dots x_v$ este mai mic din punctul de vedere lexicografic decât şirul $y_1, y_2 \dots y_v$ dacă există un indice $k \ (1 ≤ k ≤ v)$ astfel încât $x_i = y_i$, pentru orice $1 ≤ i < k$ şi $x_k < y_k$.

Exemplul 1

mun.in

1
5
A B B A A

mun.out

2

Explicație

Sunt trei delegați cu codul A și doi delegați cu codul B (sunt $2$ delegații)

Exemplul 2

mun.in

2
5
ABC BA AB BCA ABC

mun.out

1 4

Explicație

Codurile ABC, BCA și ABC sunt formate din aceleași litere, deci delegații cu aceste coduri sunt din aceeași țară. Celelalte două coduri sunt pentru doi delegați proveniți din altă țară. Rezultă că sunt două țări reprezentate la conferință. Pentru a respecta protocolul putem așeza cel mult $4$ persoane la masa rotundă. A cincea persoană va primi statutul de supervizor.

Exemplul 3

mun.in

3
5
ABC XA AX BCA BAC

mun.out

ABC AX BAC XA

Explicație

Mai există și alte modalități de aranjare circulară(cum ar fi ABC XA BCA AX), dar aranjarea delegaților în ordinea ABC AX BAC XA este cea mai mică din punctul de vedere lexicografic.