Problem Description

In the Lanqiao Kingdom, the size of a number depends not only on its numerical value, but also on the number of “closed shapes” it forms.

A closed shape refers to a completely enclosed space inside a digit. For example, digits $1$, $2$, $3$, $5$, $7$ do not form any closed shapes, while digits $0$, $4$, $6$, $9$ each form $1$ closed shape, and digit $8$ forms $2$ closed shapes. Note that the number of closed shapes can be added up. For example, for the number $68$, since $6$ forms $1$ closed shape and $8$ forms $2$ closed shapes, the total number of closed shapes formed by $68$ is $3$.

When comparing two numbers, if their numbers of closed shapes are different, then the number with more closed shapes is larger. For example, the numbers $41$ and $18$ have $1$ and $2$ closed shapes respectively, so $41$ is smaller than $18$. If two numbers have the same number of closed shapes, then the number with the larger numerical value is larger. For example, the numbers $14$ and $41$ both have $1$ closed shape, but $14 < 41$, so $14$ is smaller than $41$. If two numbers have the same number of closed shapes and the same numerical value, then they are considered equal.

Xiao Lan is very interested in the rules for comparing numbers in the Lanqiao Kingdom. Now, you are given $n$ numbers $a_1, a_2,\cdots, a_n$. Please sort these $n$ numbers in non-decreasing order according to the Lanqiao Kingdom’s rules, and output the sorted result.

Input Format

The first line contains an integer $n$, indicating the number of given numbers.

The second line contains $n$ integers $a_1, a_2,\cdots, a_n$, separated by a single space, representing the numbers to be sorted.

Output Format

Output one line containing $n$ integers, separated by a single space, representing the result after sorting in non-decreasing order according to the Lanqiao Kingdom’s rules.

3
18 29 6

6 29 18

Hint

[Sample Explanation]

For the given sequence $[18, 29, 6]$, the number $18$ has $2$ closed shapes, $29$ has $1$ closed shape, and $6$ has $1$ closed shape. Sorting by the number of closed shapes from small to large yields $[29, 6, 18]$.

Since $29$ and $6$ have the same number of closed shapes, we further sort them by numerical value, and finally get $[6, 29, 18]$.

[Constraints and Conventions]

For $50\%$ of the testdata, $1 \le n \le 2 \times 10^3$, $1 \le a_i \le 10^5$.
For all testdata, $1 \le n \le 2 \times 10^5$, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5