25675번 - Four Plus Four 다국어투 스텝

Queen Marianna has three daughters, the princesses. Marianna keeps her royal seal in a safe. The safe is protected by a password: it is an eight-letter English word from the royal dictionary. The password changes every few days.

The Queen regularly goes on vacation, and in the meantime, the princesses learn to reign the kingdom. No one of them knows the password, however, Marianna wants any two princesses to be able to open the safe in case they have an agreement. For that, on three cards, she writes three keys: four-letter English words from the royal dictionary. Each key consists of the password letters: from the eight letters, four are selected and possibly rearranged, so that the result is a dictionary word. After that, the Queen puts the cards into a hat, and then the three princesses, in sequence, take a random card and keep it to themselves, not showing it to others.

Having the royal dictionary at hand, devise an arrangement for the Queen and the princesses so that, after Marianna hands out the keys, any two princesses could determine the password using the two keys they have.

In this problem, your solution will be run twice on each test. Each line of input is terminated by an end-of-line character. The dictionary is the same in every test and in the example: the words are taken from the freely distributed word list known as ENABLE2K. All words in input and output consist of lowercase English letters.

During the first run, the solution acts for Queen Marianna. The first line contains the word "password". The second line contains an integer $n$: the number of passwords for which to select the keys ($1 \le n \le 10\,000$). Each of the next $n$ lines contains a single password: an eight-letter word from the royal dictionary. A word can be given as a password only if it is possible to construct at least three distinct keys from its letters.

After that, the royal dictionary is given. The description takes four lines and is the same in every test. The first of these lines contains an integer $n_8$: the number of eight-letter words in the dictionary ($n_8 = 28\,558$). The second line is a space-separated list of the eight-letter words themselves in lexicographical order. The third line contains an integer $n_4$: the number of four-letter words in the dictionary ($n_4 = 3919$). The fourth line is a space-separated list of the four-letter words themselves in lexicographical order.

Print $n$ lines: for each password, print three keys that Marianna writes on the cards, in any order, separated by spaces. Each key is a four-letter word from the royal dictionary consisting of the password letters: from its eight letters, four are selected and possibly rearranged, so that the result is a dictionary word. There are no other restrictions on key selection: for example, a password could turn into three keys which are all the same, and another could turn into that same key and two different keys.

During the second run, the solution acts as the prinecsses. The first line contains the word "keys". The second line contains an integer $m$: the number of pairs of keys ($1 \le m \le 60\,000$). Each of the next $m$ lines contains a pair of keys separated by a space: each such pair is selected by the jury program from some key triple printed during the first run. A pair is selected as follows: first, one key is removed, and second, the remaining two keys may be swapped. The selection is deterministic: if two solutions produced the same output during the first run, they will get the same input during the second run.

After that, the royal dictionary is given. The description takes four lines, and is exactly the same as during the first run.

Print $m$ lines: for each pair of keys, print the right password.

For each test, the input during the second run depends on the solution's output during the first run.

Below we show two runs of a certain solution on the first test. The dictionary is shown only partially for brevity. The full version of the example can be seen in 001.phase1.full.input 001.phase2.full.input.

Note that the last eight-letter word in the dictionary, "zyzzyvas", is an example of a word that can not be given as a password: from its letters, it is only possible to construct one key, "yays". Recall that a word can be given as a password only if at least three keys can be constructed from its letters. There are $70$ eight-letter words in the dictionary for which this condition does not hold.