가장 흔한 접두어

문제 정보

문제

"형아, 형아, 영어 단어에서 맨 앞에 오는 글자는 뭐가 제일 많아?"

"음.. e가 아닐까?"

"그러면 제일 앞에 오는 두 글자는?"

"음..."

"세 글자는? 네 글자는?"

"...?!"

동생의 집요한 질문에 귀찮아진 형은 프로그래밍을 잘하는 당신에게 영어사전을 주면서 3시간 이내에 답을 알려 달라고 했다. 사전에는 N 개의 영어 단어가 정렬된 상태로 주어지고, 그 중에 가장 긴 단어의 길이는 M 이다. 어떤 단어의 맨 앞에서 k 글자만 떼어낸 문자열을 k-접두어 라고 한다. 따라서 길이가 l 인 단어는 1-접두어부터 l-접두어까지 모두 l 개의 접두어를 가진다. 사전에 있는 모든 접두어를 세어 보고, 1-접두어 부터 m-접두어 까지 각각에 대해 사전에서 가장 자주 등장하는 접두어를 찾는 프로그램을 작성하라.

사전에는 같은 단어가 서로 다른 뜻으로 두 번 이상 등장하기도 한다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 C (1 <= C <= 60) 가 주어진다. 각 테스트 케이스의 첫째 줄에는 정수 N 과 M 이 주어진다. (2 <= N <= 3000,1 <= M <= 200) 그 후 N 줄에 하나씩 사전의 영어 단어들이 주어진다. 모든 단어는 소문자로 구성된다.

출력

각 테스트 케이스에 대해 M 줄에 걸쳐, 1-접두어부터 m-접두어까지 각각에 대해 가장 자주 등장하는 접두어를 출력한다. 답이 될 수 있는 접두어가 여러가지면, 그 중에서 사전 순으로 가장 먼저 나오는 것을 출력한다.

예제 입력

2 
6 4 
dark
date
dave
doc 
doc 
dock
7 3 
ab 
ab 
ac 
acc 
bc 
c 
cba

예제 출력

d 
da
doc 
dark
a 
ab 
acc

노트