Recently, Braga and Hamilton created their own language consisting only of lowercase Latin letters so they can speak about people without them knowing. However, Braga noticed that Hamilton was having trouble spelling some words of this very exotic language. Since Braga is a very proactive student, he decided to help Hamilton by creating an algorithm to autocomplete after he types some initial letters.
The logic behind his algorithm is very simple: given the string $$$s$$$ that Hamilton typed, the algorithm returns the smallest word in SupersecretLanguage that has $$$s$$$ as a prefix.
Hamilton was not convinced this would really speed up his writing...
Can you please return the number of characters that Braga's algorithm will type in?
The first line contains two integers, $$$n$$$ $$$(1 \leq n \leq 10^4)$$$, $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ - the number of words in SupersecretLanguage and the number of queries that will be made.
The next $$$n$$$ lines each contain one string $$$s_i$$$ $$$(1 \leq |s_i| \leq 10^5)$$$, a word in the dictionary. These words are not necessarily ordered.
The next $$$q$$$ lines each contain one string $$$r_i$$$ $$$(1 \leq |r_i| \leq 10^5)$$$, the words Hamilton typed into the autocompleter.
It is guaranteed that $$$\displaystyle\sum_{i = 0}^n |s_i| \leq 4\cdot10^5$$$ and $$$\displaystyle\sum_{i = 0}^q |r_i| \leq 10^6$$$.
For each string $$$r_i$$$ output the number of characters that will be autocompleted by Braga's algorithm. If $$$r_i$$$ is not a prefix to any string in the dictionary, print $$$-1$$$.
3 4 cosenza cosenzazinho brasil cos cosenzazin brasil ime
4 2 0 -1
3 6 flamengo fluminense jovemaocompletardezoitoanosvocepode fla fl flu mengo fluminense jovem
5 6 7 -1 0 30
| IME++ Starters Try-outs 2023 |
|---|
| Закончено |
