## IPSC 2005

## Problem F – Find The Right Words

Danka and Janka spend most of their time inventing and playing new games. The most recent game
they play has these rules: At first player One chooses two letters. Player Two gives him a sequence
of **K** letters **l**_{i}. Player One has to say **K** different words
**W**_{i} such that the word **W**_{i} contains the letter
**l**_{i} and the two letters chosen at the beginning of the game.
(The order of these letters in the word doesn't matter. If some of the three letters are
equal, it is sufficient if the word contains the corresponding letter once.)
Player Two scores
as many points as is the sum of the lengths of the words. Then they swap
the roles and start again. The player with the most points wins.

They made a record of every game they played. Sadly, Danka lost all the games. Now she thinks that Janka
cheated in some of the games. So Danka tried to check all previous games – but she found out that they
forgot to record the chosen words. They recorded only the letters chosen by both players. Now she needs
your help to find out how many points Player Two could get in each of the games.

### Task specification:

You are given a wordlist with allowed words and specifications of some games. The specification of a
game consists of two letters **A**, **B** chosen at the beginning of the game and of a sequence
of **N** letters **L**_{i}. For each game your task is to output **N** different words
**W**_{i} from the given wordlist. The **i**-th word W_{i} must contain the letters
**A**, **B** and **L**_{i}. The sum of the lengths of the words must be minimal.

### Input specification:

The first line of the input file contains one integer **X** denoting the number of words
in the wordlist. On the next **X** lines there is the wordlist – **X** words, one word per line.
On the **X+2**-nd line there is one number **M** denoting the number of games played.
Next **M** lines contain the specifications of the games, one game per line. The specification
of the **i**-th game consists of two letters **a**_{i}, **b**_{i} and a
sequence of **k**_{i} letters **l**_{ij}. All letters are separated by single
spaces.

### Output specification:

Output **M** blocks, one for each game in the input.
If the **i**-th game doesn't have a valid solution, its block shall contain one line with the number **-1**.
Otherwise the block starts with the number **k**_{i} of words followed by
**k**_{i} different words from the wordlist, separated by whitespaces.
The **j**-th of these words must contain characters **a**_{i}, **b**_{i}
and **l**_{ij} and the sum of the lengths of the words must be as small as possible.

Note: string comparison should be done case sensitive.

### Example

**Input:**
3
hello
competition
contest
5
c t e
c t E
c t e e
h l a
e e c

**Output:**
1 contest
-1
2 contest
competition
-1
1 contest

**Credits:**

**Problemsetter(s):** misof

**Contest-related materials:** Palo, Lukas

**Special thanks:** to the puzzle journal Relax for the game Abeceda that inspired this task