Phone Number Mnemonics

Assume the digits on a telephone are assigned lowercase English letters as follows.

1 ij   2 abc   3 def
4 gh   5 kl    6 mn
7 prs  8 tuv   9 wxy
       0 oqz

Using this mapping, a phone number can be memorized as one or more words. To convert a word to digits, replace each letter by its assigned digit and concatenate the results. When several words are used, the concatenation of their digit strings must be exactly the given phone number.

You are given a phone number and a list of words you often use. If the number can be represented, find a representation that uses as few words as possible.

The first line contains a phone number with no spaces. Its length is at most 100.

The second line contains the number of words n (1 <= n <= 50,000).

Each of the next n lines contains one lowercase English word with no spaces. Each word has length at most 50. The total input size is at most 300 KB.

If the phone number can be represented, print the number of used words K on the first line. Then print the selected words in order, one per line.

If there is no representation, print 0 on the first line and No solution. on the second line.