pisicesc

Natașa este o pisică foarte vorbăreață: ea poate pronunța toate vocalele (a, e, i, o, u) și consoana m. Am observat că mesajul pe care Natașa încearcă să mi-l transmită este o secvență dintr-o „frază” scrisă în limbaj pisicesc, care are un număr maxim de apariții în frază. Dacă există mai multe secvențe cu număr maxim de apariții, mesajul este secvența cu lungimea cea mai mare. Iar în cazul în care există mai multe secvențe cu același număr maxim de apariții și aceeași lungime maximă, mesajul este prima dintre ele în ordine lexicografică. Pentru a interpreta cât mai corect mesajele Natașei, este necesar un program care să analizeze o „frază” în limbaj pisicesc.

Cerință

Scrieți un program care citește un șir de caractere, ce reprezintă o frază în limbaj pisicesc și rezolvă următoarele cerințe:

1. determină numărul de vocale distincte existente în frază;
2. determină de câte ori apare secvența mau în frază;
3. determină mesajul transmis de Natașa, conform regulilor de mai sus.

Date de intrare

Fișierul de intrare pisicesc.in conține pe prima linie un număr natural $C$ reprezentând cerința care trebuie rezolvată ($1$, $2$ sau $3$), iar pe a doua linie, un șir de caractere format doar din litere mici (vocale și consoana m), reprezentând o „frază” în limbaj pisicesc.

Date de ieșire

Fișierul de ieșire pisicesc.out conține o singură linie pe care se află:

• dacă $C = 1$ sau $C = 2$: un număr natural reprezentând răspunsul la cerința $C$;
• dacă $C = 3$: un șir de caractere reprezentând mesajul din frază.

Restricții și precizări

• $2 \le$ numărul de litere din frază $\le 2 \ 000$;
• O secvență este constituită din două sau mai multe litere, situate în frază pe poziții consecutive; lungimea secvenței este egală cu numărul de litere din secvență;
• Secvența $a_1 a_2 \dots a_n$ este mai mică din punct de vedere lexicografic decât secvența $b_1 b_2 \dots b_n$ dacă există $k \ge 1$ astfel încât $a_i = b_i$, pentru $1 \le i < k$ și $a_k < b_k$.

Exemplul 1

pisicesc.in

1
mamimamamoimami

pisicesc.out

3

Explicație

$C = 1$. Șirul conține $3$ vocale distincte (a, i, o).

Exemplul 2

pisicesc.in

2
mamaumiaummau

pisicesc.out

2

Explicație

$C = 2$. Secvența mau apare de două ori în frază.

Exemplul 3

pisicesc.in

3
mamimamamoimami

pisicesc.out

mam

Explicație

$C = 3$. Secvențele mam, am și ma au număr maxim de apariții ($4$). Dar secvența mam are lungimea $3$, mai mare decât a secvențelor ma și am, care au lungimea $2$.