Waifu DNA

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.

Input Specification

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 Specification

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.

Sample Input 1

2
abacaba
Nadezhda abacab
Svetlana aaaaaa

Sample Output 2

Nadezhda

Sample Explanation 1

Since there is only one edit distance between abacaba and abacab compared to 3 edit distance between abacaba and aaaaaa, Nadezhda must be eliminated.

Sample Input 2

3
DNA
Leafy dna
Firey abn
bubble bub

Sample Output 2

Firey
Leafy
bubble

Sample Explanation 2

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.