Naum's cellphone has a keypad just like on the image below. When he's typing someone's name, Naum needs to press just once the key that contains the letter which he's typing at the moment.
Everyone was very impressed by this amazing functionality, except for you. So, Naum challenged you to solve this problem, if you really want to prove that this functionality isn't that awesome after all.
Given a list of $$$N$$$ Naum's cellphone contacts and $$$Q$$$ sequences of pressed keys, you must answer, for each sequence, the number of contacts whose name could actually be being typed by Naum.
Formally, Naum could be typing a name $$$s$$$ with the sequence of letters $$$t$$$ if there is a replacement of the keys in $$$t$$$ for the letters they represent, resulting in string $$$t'$$$, where $$$t'$$$ is a prefix of $$$s$$$.
The first line of input contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le Q \le 2 \cdot 10^5$$$), being the size of Naum's cellphone contact list and the number of sequences to be analyzed, respectively.
Then, $$$N$$$ lines follow, where the $$$i$$$-th of them contain a string $$$s_i$$$ $$$(0 < s_i \le 10 ^ 5)$$$, the name of the $$$i$$$-th contact, which consists only in lowercase english letters, from A to Z.
Finally, $$$Q$$$ lines follow, where the $$$i$$$-th of them contains a string $$$t_i$$$ ($$$0 < t_i \le 10^5$$$), the $$$i$$$-th sequence of keys typed by Naum, which consists of numbers from $$$0$$$ to $$$9$$$ (inclusive).
It is guaranteed that $$$\sum_{i=1}^{N} |s_i| \le 10^6$$$ and $$$\sum_{i=1}^{Q} |t_i| \le 10^6$$$.
You must output $$$Q$$$ integers, the answer for each one of the given sequences of keys.
5 5 amanda diogo lucas carlos gabriel 2 3 234 34 22
2 1 0 1 1
| UFPE Starters Final Try-Outs 2019 |
|---|
| Закончено |
