This page is still under construction.

Parts of this page are still being built. What you see may change.

Flag Quiz

Interview

Time limit1sMemory limit256 MB

Summary
Print the alternatives whose maximum position-wise difference to any other alternative is smallest.
Level

Easy2 of 10

Topics
Brute force, Array
Solved
No attempts yet

Problem

On the low budget intergalactic game show "Flag Quiz!", contestants answer questions like "What colors, symbols and shapes appear on the flags of Empire X?". An empire here is any subset of entities that share a planet, or that the Supreme Map Maker grouped together for some other reason. For example, "Empire Earth Meridian 0" is every nation that the zeroth meridian cuts through on Earth, and in that system the zeroth meridian runs through Stockholm. Knowing real geography, politics or culture can get in your way.

Most of the time you can find the answer by looking only at the alternatives. The underpaid question authors build every alternative by making a small number of changes to the correct answer, where one change replaces one part of the answer with something else. Turning "green, blue, stripes" into "green, yellow, stripes" takes one change, and turning it into "life, universe, stripes" takes two. The authors never reorder the parts, so position matters: turning "green, blue, stripes" into "stripes, blue, green" takes two changes even though the two answers list the same things. Comparison is case sensitive, so "green, blue, stripes" and "Green, Blue, Stripes" differ in 3 parts.

The incongruousity of an alternative is the largest number of changes needed to turn it into any one of the other alternatives. Find the alternatives with the smallest incongruousity.

Input

The first line holds the question. The second line holds one integer NN (1≤N≤1001 \le N \le 100), the number of alternatives. Each of the next NN lines holds one alternative.

An alternative is a list of parts separated by a comma and a space. Every alternative has the same number of parts, and that number is at most 100. A part is a string of letters a-z and A-Z, digits 0-9 and spaces, it has no leading or trailing space, and its length is at most 50 characters.

Output

Print every alternative whose incongruousity is smallest, one per line, in the order they appear in the input. If there is only one alternative, its incongruousity is 0 and it is printed.

Examples4

  1. Example 1

    Input
    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
    Expected output
    Red stripe, black stripe, yellow

  2. Example 2

    Input
    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
    Expected output
    Black, white, red, shrubbery

  3. Example 3

    Input
    Only one option?
1
Solo answer
    Expected output
    Solo answer

  4. Example 4

    Input
    Two very different flags?
2
red, blue, green
cyan, magenta, yellow
    Expected output
    red, blue, green
cyan, magenta, yellow