Hide

Problem B
Flag Quiz

/problems/flagquiz/file/statement/en/img-0001.jpg

In the intergalactic low budget streaming show “Flag quiz!”, contestants need to answer questions along the lines of “What are the joint colors, symbols and shapes occurring on the flags of Empire $X$ ?”. An empire in this context is simply some subset of entities on the same planet, or otherwise related, according to the fantasies of the Supreme Map Maker. For instance, according to the system set by the Supreme Map Maker, “Empire Earth Meridian 0” are all nations cut by the zeroth meridian on Earth. This is not necessarily the same system used locally on each planet, for instance the zeroth meridian goes through Stockholm in this system. Knowledge of geography, politics or culture can actually be an obstacle on your way to victory in this challenge!

However, sometimes (actually, most of the time) you can figure out the answer to a quiz question just by looking at the alternatives. Being a low budget show, the underpaid quiz question authors strive to minimize their effort in coming up with the alternatives for each question. They construct each alternative by making a small number of changes to the correct answer, where a change consists of replacing one part of the correct answer with something else. For example, transforming “green, blue, stripes” into “green, yellow, stripes” has one single change, while changing the same answer into “life, universe, stripes” has two changes. The question authors never permute the parts, so order matters. In other words, transforming “green, blue, stripes” into “stripes, blue, green” has two changes even though they are both technically the same answer. Note that the answers are case sensitive, so “green, blue, stripes” and “Green, Blue, Stripes” need 3 changes.

Your task is to write a program that automatically finds the most likely answers to questions constructed in this way. Define the incongruousity of an alternative as the maximum number of changes needed to transform that alternative into any of the other alternatives. We then seek the alternative(s) with the smallest incongruousity.

Task

Given a question and a set of potential answers to it, find the answer that is easiest to change into any other answer.

Input

The first line is the question to be answered. The next line contains one positive integer $1 \leq N \leq 100$ , giving the number of answer alternatives. The next $N$ lines contain one alternative each. The alternatives are lists of parts, separated by a comma and a space. All answers have the same number of parts, at most 100. All parts are strings of letters a-z and A-Z, digits 0-9 and spaces. Each part doesn’t contain leading or trailing spaces (except the space after a comma that separates 2 parts). The maximal length of a part is 50 characters.

Output

Output the alternative that requires the smallest maximum amount of changes to be turned into any other answer. If there are several least incongruous alternatives, output them all in the same order as in the input.

Sample Input 1	Sample Output 1
The flag of the empire Angola? 4 Green stripe, black stripe, yellow Red stripe, black stripe, yellow Red stripe, black stripe, white Red stripe, green stripe, yellow	Red stripe, black stripe, yellow

Sample Input 2	Sample Output 2
The flag of the Knights who say Ni? 4 Black, white, pink, shrubbery Black, white, red, shrubbery Pink, white, red, shrubbery Black, pink, red, shrubbery	Black, white, red, shrubbery

Problem BFlag Quiz

Task

Input

Output

Problem B
Flag Quiz