Problem D
Dialling Digits

CC BY 2.0 by Elliot Brown on Flickr, modified

Disaster struck at the Billboards And Phone-numbers Company! Due to a bug in their database system, they lost the corresponding mnemonic phrases for each of the registered phone numbers. These mnemonic phrases are typically used on billboards, to make a phone number for an advertisement easier to remember by people who read them. To dial the phone number from a mnemonic phrase, you simply have to press the number keys corresponding to each letter, as shown in Figure 1. For example, the phone number “1-800-BAPC” would be dialled as “1-800-2272”.

Using this information and a given list of valid words, reconstruct the possible mnemonic phrases for each registered phone number. Each mnemonic phrase consists of exactly one word from the word list. In the input, you will only receive the part of the phone number that should be exactly linked to possible mnemonic phrases, so it does not include the “1-800-” prefix (or any other prefix).

Figure 1: The keypad of a telephone, where some numbers are assigned several letters.

Public Domain by Sakurambo on Wikimedia Commons, modified

Input

The input consists of:

• One line with two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$, $n \cdot m \leq 10^5$), the number of words and the number of phone numbers.

• $n$ lines, each with a word $w$ ($1 \leq |w| \leq 10$), consisting only of English lowercase letters (a-z). The words are unique and given in alphabetical order.

• $m$ lines, each with a phone number $p$ ($1 \leq |p| \leq 10$), consisting only of digits that correspond to letters in a mnemonic phrase (2-9).

Output

For each phone number, output the number of words that are a valid mnemonic phrase for this phone number, followed by these words in alphabetical order.

5 3
algorithm
bapc
benelux
contest
progaming
2272
424242
2363589

1 bapc
0
1 benelux

3 1
peer
reds
refs
7337

3 peer reds refs

7 3
black
judge
my
of
quartz
sphinx
vow
25225
782789
774466

1 black
1 quartz
0

5 1
and
bland
e
land
of
63

1 of