6. Optimalizácia písania na klávesnici

Samko sa nedávno zamestnal ako programátor pre jeden veľký wébový portál. Už počas prvého týždňa zistil, že to nebude jednoduchá práca. Má totiž na starosti opravovanie starého zdrojového kódu s množstvom chýb. Jeho bežný pracovný deň vyzerá tak, že zapne počítač, otvorí si mail a nájde desiatky škaredých správ od frustrovaných užívateľov. Tí sa väčšinou oprávnene sťažujú na množstvo bugov, ktoré sa na stránke nachádzajú. Samko samozrejme musí všetky takéto prípady preveriť, bugy nájsť a opraviť. Preto sa pomocou ssh na diaľku pripojí k príkazovému riadku (terminálu) servera a prehľadávaním logov a zdrojového kódu zisťuje, kde nastala chyba.

Keďže práce je veľa, Samko sa snaží využívať svoj čas efektívne. Napríklad sa naučil bezchybne písať všetkými desiatimi prstami. Teraz však objavil novú funkciu jeho terminálu – slovník často používaných slov (príkazov). Keď do terminálu napíše začiatok nejakého slova zo slovníku a stlačí TAB, tak sa mu tam toto slovo celé dopíše. Ak sa viac slov v slovníku začína rozpísaným slovom, tak sa dopíše lexikograficky najmenšie z nich. Ak žiadne slovo v slovníku nezačína rozpísaným slovom, tak v tom prípade kláves TAB nespraví nič. Samko po dlhej úvahe dospel k tomu, že táto funkcia mu vie ušetriť veľa zbytočných stlačení klávesnice. Napríklad ak má v slovníku lexikograficky najmenšie slovo auto a chce napísať slovo aut, tak to môže spraviť tak, že stlačí TAB a Backspace (kláves na zmazanie posledného znaku). Nemiesto troch stlačení tak spraví iba dve.

Samka by zaujímalo, koľko času mu táto funkcia vie ušetriť. Preto by si chcel spraviť štatistiku o tom, koľko stlačení potrebuje na napísanie určitých slov. Keďže má však ešte veľa roboty s hľadaním bugov, potreboval by, aby mu s tým niekto pomohol. Zvládnete to?

Úloha

Na vstupe je terminálový slovník často používaných slov a zoznam slov, ktoré Samka zaujímajú. Pre každé slovo zo Samkovho zoznamu vypíšte, koľko stlačení klávesnice je potrebných na jeho napísanie. Samkov terminál nepodporuje používanie šípok a iných kláves na presúvanie kurzora. Jediné klávesy, ktoré Samko používa sú písmená, TAB a Backspace (na zmazanie posledného znaku).

Formát vstupu

Na prvom riadku vstupu sa nachádzajú čísla \(n\) a \(q\), – prvé určuje počet slov v slovníku \((1 \leq n \leq 1\,000\,000)\) a druhé počet slov v Samkovom zozname \((1 \leq q \leq 1\,000\,000)\). V každom z nasledujúcich \(n\) riadkoch je jedno slovo zo slovníka. Na ďalších \(q\) riadkoch sa nachádzajú postupne slová v Samkovom zozname. Všetky slová na vstupe sa skladajú z malých písmen anglickej abecedy a majú menej ako \(60\,000\) písmen. Celkový počet písmen na vstupe nepresiahne \(2\,150\,000\).

Formát výstupu

Pre každé z \(q\) slov v Samkovom zozname vypíšte jeden riadok – najmenší možný počet stlačení kláves na napísanie daného slova.

Príklad

Input:

3 7
autobus
auto
autostrada
auto
aut
a
autobusar
autobus
autob
utobus

Output:

1
2
1
5
3
2
6

Všimnite si, že slovo auto je v slovníku lexikograficky najmenšie. Preto na jeho napísanie stačí jedno stlačenie TAB.

Slovo autobusar vieme napísať nasledujúcov postupnosťou kláves: TAB, b, TAB, a, r.

Slovo utobus musíme napísať celé znak po znaku.