407151: GYM102697 122 Autocorrect

You're phone has incorrectly autocorrected some of your recent texts, and you're trying to make a more effective autocorrect system.

You're given an incorrectly spelled word. The similarity index of two words $$$s$$$ and $$$t$$$ is calculated as follows:

1. Define two variables: $$$tot$$$, representing the total pairs checked, and $$$mat$$$, representing the matches found.

2. Iterate through all pairs of letters in $$$s$$$ and $$$t$$$.

3. Increment $$$tot$$$ by one, and if the letters are equal, increment $$$mat$$$ by one as well.

The similarity index is calculated as mat / tot.

Given several words, your autocorrect system will choose the word which is the most similar to the original word, using the algorithm described above.

The first line of input contains a single word $$$w$$$: the incorrectly spelled word, consisting only of lowercase characters. The next line contains a single positive integer $$$n$$$: the number of correctly spelled words in the dictionary. The next $$$n$$$ lines each contain a correctly spelled word $$$s$$$: a dictionary entry, consisting of only lowercase characters.

Output $$$n$$$ lines. Each line should contain a word from the dictionary, and its similarity index, rounded to two decimal places. The words should be sorted from highest to lowest by their similarity index. If two words have the same similarity index, sort them alphabetically in reverse order.

hello
5
helo
helllo
yello
hellow
helpo

helllo 0.30
helo 0.25
yello 0.24
hellow 0.23
helpo 0.20

coderams
8
cauliflower
coders
codered
classroom
codeforces
contest
code
coding

coders 0.12
codered 0.12
code 0.12
codeforces 0.11
classroom 0.11
contest 0.07
coding 0.06
cauliflower 0.06