Description
Today, as usual, the cookie monster is picking the cookies to eat for this meal. He is so tired and unable to select the cookies he wants since he was busy preparing for his midterm and didn’t sleep last night. As his good friend, you decided to help him so he doesn’t need to worry about his lunch.
There are n cookies in the shop. For each cookie, there is a number di, representing how yummy the ith cookie is. In general, the larger di is, the more delicious the ith cookie is. However, due to some unknown reasons, the cookie monster especially loves cookies that contain the digit 7 in their di. For example, the digit ‘7’ appears twice in 7927 and appears once in 70. If there are more digits ‘7’ appearing in di for a cookie, the cookie monster would tend to choose that cookie first.
Moreover, here’s your cookie-choosing strategy:
- For any two cookies, always choose the one that with more ‘7’ appears in di first.
- If there are two cookies containing the same amount of ‘7’ in their di, choose the one with larger di.
However, due to some unknown reason, the number di does not always be marked on the wrapper of the cookie directly. Let si denote the string printed on the wrapper of the ith cookie. si is a string containing only integers and dots. There may be no dots or exactly 2 dots in si. If there are 2 dots in si, reversing the interval between 2 dots and then removing the dots can transform si into di. For example, if si = 31.124.12, then di = 3142112. If si doesn’t contain any dots, then di = si.
Now the cookie monster wants to choose k cookies at most for this meal, help him choose the cookies he is going to eat.
For testcase 1 and 2, there are no dots in si for every cookie.
For testcase 3 and 4, if there are 2 dots in si, it is guaranteed that the substring between 2 dots is a palindrome, i.e. the substring remains the same after the reversal.
There are no further restrictions for the remaining testcases.
Input
The first line contains two integers n, k, representing the number of cookies in the shop and the amount cookies you are going to choose, respectively.
The next n lines each contains a string, The 1+ith line specifies the value of si.
Constraints:
1 ≤ n ≤ 1000
1 ≤ di ≤ 10300
1 ≤ k ≤ n
1 ≤ |si| ≤ 300
It is guaranteed that there are no leading zeros in si and after transforming si to di.
Output
Output k lines, the value of di for each cookie you choose, in the order that the cookie monster likes more prints first.