puzzle

Maria a primit cadou de ziua ei o cutie cu piese de puzzle, etichetate cu numere naturale. Pentru a-l rezolva, trebuie să lipească între ele, în ordinea în care le extrage din cutie, cât mai multe piese, formând astfel grupuri de piese.

Două piese de puzzle se pot lipi între ele dacă numerele de pe etichetele lor au cel puțin trei cifre comune. La operația de lipire a două piese se obține un grup de piese care va fi etichetat cu numărul obținut prin alipirea primelor patru cifre de pe prima etichetă cu ultimele patru cifre de pe cea de a doua etichetă (dacă numerele de pe etichete nu au cel puțin patru cifre se păstrează doar cele existente fără a adăuga altele). O piesă se poate lipi de o altă piesă sau de un grupul de piese anterior creat (dacă acesta există), sau poate forma singură un grup.

De exemplu, dacă pe etichete avem numerele $133454$ și $3523143$ atunci putem lipi cele două piese deoarece au în comun cinci cifre (o cifră $1$, două cifre $3$, o cifră $4$ și o cifră $5$). În urma lipirii obținem un grup cu eticheta $13343143$.

Pentru a rezolva jocul Maria extrage pe rând din cutie câte o piesă. Dacă aceasta se poate lipi de ultimul grup format atunci o lipește de el și actualizează eticheta grupului, altfel pune deoparte grupul respectiv și începe să formeze un nou grup pornind cu piesa extrasă.

După ce formează grupurile Maria alege etichete de grupuri în următoarea ordine: prima dată alege eticheta cu număr maxim de cifre distincte. Dacă sunt mai multe, o alege pe cea cu valoarea cea mai mică. Dintre etichetele rămase alege următoarea etichetă după aceiași regulă. Continuă procedeul până când a ales $K$ etichete.

Cerințe

Cunoscând cele $N$ numere naturale care se găsesc pe etichetele pieselor de joc, în ordinea în care aceste se extrag din cutie, să se determine:

1. Numărul de grupuri pe care le obține Maria după ce rezolvă jocul de puzzle;
2. Cele $K$ numere înscrise pe etichetele grupurilor alese de Maria.

Date de intrare

În fișierul puzzle.in se găsesc pe prima linie, separate prin câte un spațiu, $C$, $N$ și $K$, unde $C$ reprezintă cerința ce trebuie rezolvată, $N$ numărul de piese din joc, $K$ numărul de valori cerute la cerința $2$. Pe linia următoare, separate prin câte un spațiu, sunt cele $N$ numere înscrise pe etichetele pieselor de joc, în ordinea în care se extrag din cutie.

Date de ieșire

Dacă cerința este $1$, fişierul de ieşire puzzle.out va conţine pe prima linie un număr natural $G$, reprezentând numărul de grupuri obținut după finalizarea jocului.

Dacă cerința este $2$ pe prima linie a fișierului de ieșire puzzle.out se vor scrie, separate prin câte un spațiu, cele $K$ numere înscrise pe etichetele grupurilor alese de Maria.

Restricții și precizări

• $1 \leq C \leq 2$
• $1 \leq N \leq 100 \ 000$
• $1 \leq K \leq 10$
• Numerele de pe etichetele pieselor sunt numere naturale cu cel mult nouă cifre;
• Pentru toate datele de test există soluție.

Exemplul 1

puzzle.in

1 6 1
13345 23143 4343 784532 432 7826

puzzle.out

2

Explicație

Piesa cu eticheta $13345$ se poate lipi cu piesa cu eticheta $23143$, obținând astfel grupul cu eticheta $13343143$ la care se poate lipi piesa cu eticheta $4343$ și obținem $13344343$ care nu se mai poate lipi cu următoarea piesă cu eticheta $784532$, dar această piesă se va lipi cu piesa etichetată cu $432$ și obținem $7845432$ care în continuare se lipește cu piesa $7826$ și obținem a doua etichetă a unui grup $78457826$.

Exemplul 2

puzzle.in

2 6 1
13345 23143 4343 784532 432 7826

puzzle.out

78457826

Explicație

În urma grupării pieselor obținem două grupuri etichetate cu $13344343$ și respectiv $78457826$. Dintre acestea $78457826$ are $6$ cifre distincte, iar $13344343$ are doar $3$ cifre distincte. Deci valoarea căutată este $78457826$.