Shelf Labels in Human Order

A library's catalogue sorts shelf labels the way people read them: B9 comes before B10, although plain string order puts B10 first. Given a list labels, return a new list with the labels in this human order.

Cut each label into chunks: maximal runs of digits (0-9) and maximal runs of other characters. "Box12-a7" has the chunks "Box", "12", "-a", "7". To decide which of two labels comes first, compare their chunks pairwise from the left, stopping at the first difference:

1. Two digit chunks compare by the whole number they spell ("007" equals "7").
2. Two text chunks compare alphabetically ignoring case: compare them after lower() with ordinary string order.
3. A digit chunk comes before a text chunk.
4. If one label runs out of chunks first, it comes first.

If all of that finds no difference (as for "a01" and "a1", or "X" and "x"), the labels are ordered by ordinary Python string comparison. Identical labels stay side by side.

Examples

Input:  labels = ["file10.txt", "file9.txt", "File1.txt", "file1.txt"]
Output: ["File1.txt", "file1.txt", "file9.txt", "file10.txt"]

Input:  labels = ["x2", "x", "x02", "10", "2b", "X"]
Output: ["2b", "10", "X", "x", "x02", "x2"]

Constraints

• 0 <= len(labels) <= 300; each label has 0 to 40 printable ASCII characters
• Digit runs may be up to 40 digits long

Goals

• Cut a label into runs of digits and runs of other characters
• Write a three-way comparison with several layers of tie-breaks
• Order a list using your own comparison