Kattis

# Spelling Bee

An example of the Daily NY Times Spelling Bee Puzzle

The New York Times publishes a daily puzzle called the “Spelling Bee.” In this puzzle, $7$ letters are shown in a hexagonal arrangement of $6$ letters around a center letter. The task is to come up with as many words as possible that

• contain only letters that are displayed in the hexagon,

• are at least of length $4$, and

• contain the center letter.

A letter may be used more than once, and not all letters need to be used.

After playing for a while, you get stuck, but then you remind yourself that the Linux distribution on your computer comes with a machine-readable file of $102\, 305$ dictionary words in /usr/share/dict/words!

You decide that even if you can’t excel at the Spelling Bee you can still excel at programming, so you decide to write a program that finds all solutions to a Spelling Bee puzzle from your dictionary.

## Input

The input consists of a single test case, which starts with a line with $7$ distinct lowercase English letters. The first of these letters is the center letter. The next line contains an integer $n$ ($1 \le n \le 102\, 305$), the size of the dictionary. This line is followed by $n$ lines, each containing a dictionary word of $l$ lowercase English letters ($1 \le l \le 24$).

## Output

Output the word list matching the Spelling Bee puzzle in the order in which they appear in the dictionary. You are guaranteed that at least one dictionary entry will match.

Sample Input 1 Sample Output 1
drulyag
27
duly
spelling
multiplexed
janna
lard
dryly
the
instances
dual
inimically
off
dullard
equipage
mauritania
drug
a
drag
pickering
yard
on
lallygag

dryad
duly
lard
dryly