You are given n version strings in a simplified semantic-versioning format: MAJOR.MINOR.PATCH, each of MAJOR/MINOR/PATCH a non-negative integer with no extra leading zero characters beyond the value 0 itself, optionally followed by a pre-release suffix -ID1.ID2. ... .IDk (a - followed by one or more dot-separated identifiers; an identifier consists of ASCII letters, digits, and hyphens, and is never empty).
Sort the versions in ascending precedence order using these rules:
- Compare MAJOR, then MINOR, then PATCH as integers. Whichever is smaller has lower precedence.
- If MAJOR.MINOR.PATCH are equal: a version WITHOUT a pre-release suffix has HIGHER precedence than one WITH a pre-release suffix.
- If both have a pre-release suffix and MAJOR.MINOR.PATCH are equal, compare their identifiers pairwise from left to right. For a pair of identifiers at the same position: if BOTH consist entirely of digits, compare them as integers; if exactly one consists entirely of digits, that one has LOWER precedence than the other (a numeric identifier is always considered lower-precedence than a non-numeric one at the same position); otherwise (neither is purely digits, or as a general fallback) compare them as plain strings using ASCII/lexicographic order. The first pair that differs decides the comparison.
Input format
Line 1: an integer n.
Lines 2..n+1: one version string per line.
Output format
The n version strings, one per line, in ascending precedence order.
Constraints
- 1 ≤ n ≤ 200
- 0 ≤ MAJOR, MINOR, PATCH ≤ 1000
- 0 to 5 pre-release identifiers, each 1 to 15 characters from
[A-Za-z0-9-]