IPSC 2005 Problem F – Find The Right Words

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