Opgave

Het veelal parate woorddeel (VPW) van een verzameling van teksten is de langste substring die in minstens een opgegeven aantal van deze teksten voorkomt.
Bijvoorbeeld, het VPW met ondergrens 2 voor de teksten

• aaabc
• aabcaa
• aacbcdd

is ‘aabc’ aangezien deze substring in minstens 2 teksten (de ondergrens dus) terug te vinden is.

     VPW(2,{’aaabc’, ’aabcaa’, ’aacbcdd’}) = {’aabc’}

Voor ondergrens 3 zijn de substrings ‘aa’ en ‘bc’ de VPWs.

     VPW(3,{’aaabc’, ’aabcaa’, ’aacbcdd’}) = {’aa’, ’bc’}

Invoer

De eerste regel bevat het aantal testgevallen N. Per testgeval volgen er dan twee regels met de ondergrens O en het aantal teksten A. Je mag ervan uit gaan dat 2 ≤ A ≤ 100 en 2 ≤ O ≤ A. Vervolgens volgen er A regels met de teksten van het testgeval. De teksten bestaan uit minimaal 1 en maximaal 100 letters.

Voorbeeldinvoer

4
2
3
aaabc
aabcaa
aacbcdd
3
3
aaabc
aabcaa
aacbcdd
2
2
axaaaaxxxxaaa
aaaaaabxxxxbaaa
2
2
aaa
bbb

Uitvoer

Elk testgeval wordt afgedrukt op een nieuwe regel. Elke regel begint met geval N gevolgd door een spatie en alle gevonden veelal parate woorddelen, gescheiden door een spatie indien meerdere gevonden. De gevonden veelal parate woorddelen worden alfabetisch geordend in de uitvoer geplaatst. Indien er geen substring gevonden wordt, druk je ‘ONMOGELIJK’ af.

Voorbeelduitvoer:

1 aabc
2 aa bc
3 aaaa xxxx
4 ONMOGELIJK