Dialling Digits

Interview

Time limit2sMemory limit1024 MB

Summary

Given a sorted word list and phone numbers, list for each number the words whose keypad digits spell that number, in alphabetical order.

Level: Easy3 of 10
Topics: Hash map, String
Solved: No attempts yet

Problem

Disaster struck at the Billboards And Phone-numbers Company! The hyphen in Phone-numbers is deliberate, used for the backronym.

A database bug erased the mnemonic phrases for every registered phone number. Mnemonic phrases usually appear on billboards, so people who read an advertisement can remember its phone number more easily. To dial a number from a mnemonic phrase, press the number key that carries each letter, as shown in Figure D.1. For example, "1-800-BAPC" is 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 is exactly one word from the word list. The input gives only the part of each phone number that must match a mnemonic phrase, without the "1-800-" prefix or any other prefix.

Figure D.1: The keypad of a telephone, where some number keys carry several letters.

Input

The first line contains 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.

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

The last $m$ lines each contain a phone number $p$ ( $1 \leq |p| \leq 10$ ), made only of digits 2-9 that match the letters of a mnemonic phrase.

Output

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

Examples4

Example 1

Input

5 3
algorithm
bapc
benelux
contest
progaming
2272
424242
2363589

Expected output

1 bapc
0
1 benelux

Example 2

Input

3 1
peer
reds
refs
7337

Expected output

3 peer reds refs

Example 3

Input

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

Expected output

1 black
1 quartz
0

Example 4
Input
```
5 1
and
bland
e
land
of
63
```
Expected output
```
1 of
```