문제

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

"음.. e가 아닐까?"

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

"음..."

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

"...?!"

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

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