Description

Cookie Monster is back! This time, he has bought all the cookies in the entire supermarket. There are a total of N cookies, and for each cookie, there is a number d_i indicating how delicious the i-th cookie is. Generally, the larger d_i, the more delicious the i-th cookie is. However, Cookie Monster considers the number 7 to be his lucky number, so he especially loves cookies that contain the digit '7' in their d_i. Moreover, if a cookie's d_i contains a '7' at a higher-order position, the Cookie Monster would tend to choose that cookie first. Considering the example of 5 cookies with 48767, 48763, 379498, 377777, and 12345689, respectively, we have

Since both 377777 and 379498 have a '7' at the same highest-order position but 379498 has a larger d_i value than 377777, Cookie Monster will choose the cookie with 379498.

We can summarize Cookie Monster's selection strategy as follows:

• For any two cookies, always choose the one that contains the digit 7.
• If both cookies contain the digit 7, he will prioritize the one with the higher-order position of the digit 7.
• If both cookies share the same highest-order position of the digit 7 or neither contains the digit 7, he will prioritize the one with a larger d_i.

Now, given the numbers d_i for N cookies, please help Cookie Monster determine the order in which he should eat the cookies.

Input

The first line contains one integers N, representing the number of cookies.
The next N lines each contains a positive integer d_i.

Constraints

• Test Case 1: there is no '7' in every d_i.
• Test Case 2: 1 ≤ d_i ≤ 10⁸.
• Test Cases 3 ~ 8: satisfy no additional constraints.
• For all test cases: 1 ≤ N  ≤ 1000, 1 ≤ d_i ≤ 10¹⁰⁰.

Output

Output N lines, indicating the order in which Cookie Monster eats the cookies. In the order that the higher priority prints first.

Remember to print a ‘\n’ at the end of the output.

Do not include any spaces at the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss