아방가르드 자동 수정

Filip과 Luka는 한 WhatsApp 그룹에서 각자 살아가는 이유를 찾았다. 둘 다 그룹의 나머지 사람들을 즐겁게 하는 것이 목표지만, 방법은 전혀 다르다.

Filip은 계산이 치밀한 사람이다. 그의 메시지는 하나하나 신중하게 고른 것이고, 보통 그룹의 다른 멤버 최소 한 명의 미소를 끌어낸다. 가끔은 자기 자신을 보고 웃기도 한다.

Luka는 말솜씨가 뛰어나고 아는 것이 많은 사람이다. 그는 재미있거나 난처했던 일을 많이 되풀이해 들려주면서, poistovječivanje sa situacijama, 즉 상황에 자신을 겹쳐 보는 기법으로 일행을 즐겁게 한다.

Luka는 분당 60단어 정도밖에 입력하지 못해서 이 기법을 온전히 쓰지 못할 때가 있다. 그래서 iPhone이 제공하는 가장 전위적인 자동 수정 기능을 설치하기로 했다.

Luka의 자동 수정 기능에는 사용 빈도 순으로 정렬된 n개의 단어가 담긴 사전이 있다. Luka가 단어를 입력할 때마다 자동 수정은 지금까지 입력한 글자로 시작하는 단어 중 가장 많이 쓰인 단어를 제안한다(그런 단어가 있는 경우). tab 키를 누르면 제안된 단어를 완성할 수 있고, 필요하면 이어서 계속 입력할 수 있다. 자동 수정은 글자가 하나 이상 입력된 뒤에만 쓸 수 있다.

Luka는 m개의 단어로 된 메시지를 입력하려 한다. 각 단어마다 그 단어를 쓰는 데 필요한 키 입력 횟수의 최솟값을 알고 싶다. Luka는 tab 키, backspace 키, 그리고 글자마다 하나씩 있는 키를 쓸 수 있다.

Luka가 각 단어를 입력하는 데 필요한 키 입력 횟수의 최솟값을 계산하도록 도와 달라.

첫 줄에는 자연수 $n$과 $m$이 주어진다 ($1 \le n \le 100\,000$, $1 \le m \le 100\,000$).

다음 $n$개의 줄에는 자동 수정이 아는 단어가 사용 빈도 순서대로(가장 많이 쓰인 단어가 먼저) 주어진다.

그다음 $m$개의 줄에는 Luka가 입력하려는 단어가 한 줄에 하나씩 주어진다.

모든 단어는 영어 소문자로만 이루어져 있다. 입력 파일의 크기는 1 MB보다 작다.

$m$개의 줄을 출력한다. 메시지의 각 단어마다 Luka가 그 단어를 입력하는 데 필요한 키 입력 횟수의 최솟값을 한 줄에 출력한다.