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.
2
abacaba
Nadezhda abacab
Svetlana aaaaaa
Nadezhda
Since there is only one edit distance between abacaba
and abacab
compared to 3 edit distance between abacaba
and aaaaaa
, Nadezhda
must be eliminated.
3
DNA
Leafy dna
Firey abn
bubble bub
Firey
Leafy
bubble
Since the edit distance between DNA
and dna
, between DNA
and abn
, and between DNA
and bub
are all equal, Leafy
, Fiery
, and bubble
must all be eliminated.