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: $t o t$, representing the total pairs checked, and $m a t$, representing the matches found.
2. Iterate through all pairs of letters in $s$ and $t$.
3. Increment $t o t$ by one, and if the letters are equal, increment $m a t$ 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*.
## Input
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
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*.
[samples]
**Definitions**
Let $ w \in \Sigma^* $ be the incorrectly spelled word, where $ \Sigma = \{a, b, \dots, z\} $.
Let $ D = \{s_1, s_2, \dots, s_n\} \subseteq \Sigma^* $ be the dictionary of correctly spelled words.
For any two words $ s, t \in \Sigma^* $, define:
- $ \text{tot}(s, t) = \min(|s|, |t|) $,
- $ \text{mat}(s, t) = \sum_{i=1}^{\min(|s|, |t|)} \mathbf{1}_{s[i] = t[i]} $,
- The similarity index: $ \text{sim}(s, t) = \frac{\text{mat}(s, t)}{\text{tot}(s, t)} $.
**Constraints**
1. $ |w| \geq 1 $, $ |s_i| \geq 1 $ for all $ i \in \{1, \dots, n\} $.
2. All characters are lowercase English letters.
3. $ 1 \leq n \leq 1000 $.
**Objective**
For each $ s_i \in D $, compute $ \text{sim}(w, s_i) $, rounded to two decimal places.
Output the dictionary words sorted in descending order of $ \text{sim}(w, s_i) $.
In case of ties, sort alphabetically in reverse (i.e., descending lexicographical) order.