Simulation - Info-Oltenia 2024 Echipe XI-XII | Cora

Amidamaru iubește să-și facă cumpărăturile la Cora. Fiind magazinul lui preferat, și-a făcut o listă cu toate produsele pe care le cumpără de obicei, reprezentate prin $n$ cuvinte.

Cum Amidamaru este un om bine organizat, a rugat-o pe mama lui să îi facă o listă completă de cumpărături pentru ziua de azi, listă în care se găsesc produse din cele $n$, fiecare putând să apară de mai multe ori. Lista trimisă de mama lui s-a stricat când Amidamaru a primit-o pe telefon, spațiile au dispărut, unele caractere s-au schimbat, iar acum lista e un șir aleator de caractere $S$.

Ajută-l pe Amidamaru să recupereze produsele care încă se mai găsesc pe listă, aflând pentru fiecare din cele $n$ cuvinte de câte ori apare în șirul de caractere $S$ care reprezintă lista amestecată și apoi afișând produsul cu cele mai multe apariții.

Cerință

Cunoscând $n$ și $S$, determinați cuvântul cu cele mai multe apariții în $S$.

Date de intrare

Pe prima linie a fișierului de intrare cora.in se găsește $S$, șirul de caractere.
Pe cea de-a doua linie, se găsește un număr întreg, $n$.
Pe următoarele $n$ linii se găsesc cele $n$ cuvinte ca și șiruri de caractere, reprezentând produsele lui Amidamaru.

Date de ieșire

Pe prima linie a fișierului de ieșire cora.out se va găsi un singur număr întreg, reprezentând numărul maxim de apariții ale unui produs.
Pe cea de-a doua linie se va afișa numele produsului cu număr maxim de apariții. În cazul în care există mai multe soluții, se va afișa produsul cu numele cel mai mic din punct de vedere lexicografic.

Restricții și precizări

• $1 \leq$ Lungimea lui $S \leq 1 \ 000 \ 000$;
• $1 \leq$ Lungimea unui cuvânt $\leq 10 \ 000$;
• $1 \leq n \leq 100$;
• Un cuvânt poate apărea în listă doar pe poziții consecutive ale șirului;
• Toate cuvintele sunt formate din caractere mici ale alfabetului englez.

Exemplul 1

cora.in

merepereshajdsperesscajubanan
4
mere
pere
banane
caju

cora.out

2
pere

Explicație

În exemplu, mere apare o singură dată, pere de $2$ ori, caju o singură dată, iar banane deloc. pere este produsul cu număr maxim de apariții.

Exemplul 2

cora.in

primetescojhdftescoffdtescogatoruhuadeprimeprimescoprime
4
gatorade
prime
tesco
sco

cora.out

4
prime

Explicație

prime și sco apar amândouă de exact $4$ ori, dar prime este mai mic lexicografic.