Ekaterine has a crush on Joseph, her classmate. Joseph also has a crush on one of the girls in his class. Ekaterine wants to find out who it is so she can eliminate them and become Joseph's crush. Luckily Joseph recently created his own Waifu with Waifu-maker 3000, and shared its own "DNA" (Alphanumeric String) with others. Ekaterine, being a stalker, has collected the DNA of all her other classmates. All she has to do is compare the DNA from Joseph's Waifu with her classmates' DNAs and find the closest match.
The first line of input contains an integer \(n\). \((1 \le n \le 1000)\)
The next line of input contains a string composed of alphanumeric characters.
The next \(n\) lines contains two space-separated strings composed of alpanumeric characters. The first one being the name of a classmate, and the second one the DNA of the classmate.
It is guranteed that all of the names and the DNAs are unique, and the length of the names and the DNAs are between \(1\) and \(50\) (inclusive).
Output in each line, the names of the classmates with the closest DNA compared to Joseph's Waifu, in lexicographical order.
Note: To compare two alphanumeric strings, count how many times a character has to be inserted, removed, or replaced.
Since there is only one edit distance between
abacab compared to 3 edit distance between
Nadezhda must be eliminated.
Since the edit distance between
abn, and between
bub are all equal,
bubble must all be eliminated.