시간 제한메모리 제한제출정답맞힌 사람정답 비율
12 초 128 MB41125.000%

## 문제

A spelling suggestion is a part of spelling correction program that generates a set of plausible replacements for words that are likely to be misspelled. One way to measure the plausibility of these replacements is to compute their edit distance against a given misspelled word. The edit distance between two words is the total number of edit operations that have to be done in order to transform one word into the other. Normally these edit operations are insertion, deletion and substitution of a single character including transposition of 2 consecutive characters.

For example, for a word wonder, if the deletion is applied at the character 'o', this word will transform into wnder. And if the substitution with 'a' is applied at 'o', it will become wander. And if the transposition is applied at er, it will become wondre.

In this edit distance strategy, the degree of similarity between two words is up to their minimum edit distance. If the minimum edit distance between word1 and word2 is lower than the distance between word1 and word3, then word1 is more similar to word2 than to word3. So the word2 is a better spelling suggestion for word1, comparing with word3.

Suppose that you are an employee of a software company which needs to build up a prototype of spelling suggestion program. This prototype tends to be a part of word processing software. The requirement is that it has to use the edit distance strategy for their spelling suggestion. But the substitution operation has to be redefined to match the behavior of mistyping. The cost of substitution of a character with another character depends on the position of them on the keyboard layout. If they are close to each other, the cost is only half of the normal one. For this purpose, the substitution is categorized into near-substitution and far-substitution. Their costs are defined as 1 and 2 respectively. And the costs for insertion, deletion and transposition are 2. In addition, this program must run fast enough to pass the time limit that is set by your manager. By the way for this prototype, an English QWERTY keyboard layout is chosen to be used.
Goal
To generate optimum spelling suggestions for each input word, where each optimum spelling suggestion is a word in dictionary that has the least minimum edit distance from the given input word. The time limit for 5,000 misspelled words is less than or equal to 5 minutes.

## 입력

Input is a standard input which contains 3 parts of data. Each of these three parts ends with a blank line.
The first part is a set of near-substitution rules, where each rule is kept in one line. Each line has two fields. Each filed is separated by a space. The total no. of rules is less than or equal to 150

• The first field is a character where it can be near-substituted with other characters.
• The second field is a sequence of characters which can be near-substituted for the character in the previous field. There is no space in this field.
• The characters that may be contained in this part are characters that can be typed in using a generic English keyboard layout, which are alpha-numeric characters and some punctuations without space or tab. They are listed as the following.

z ZaAxX

a
A
b
B
Z
angel
angle
anger
angry
ABC

x
s
z
xx
xxx
angre
angri
angrt
angel
ACB
BAC
CAB

## 예제 출력 1

x:2:A B Z a b
s:1:a
z:1:A Z a
xx:4:A B Z a b
xxx:6:A ABC B Z a b
angre:2:anger angle angry
angri:2:angry
angrt:2:anger angry
angel:0:angel
ACB:2:ABC
BAC:2:ABC
CAB:4:A ABC B