Sort Strings by Length

Given a list of strings, sort them by their length in ascending order while maintaining the relative order for strings of equal length. In other words, if two strings have the same length, they must appear in the same order as they did in the input. This problem emphasizes the use of stable sorting.

The sorting criterion is based on the length of each string. Use a stable sorting algorithm to ensure that strings with identical lengths remain in the same relative order as in the original input.

Mathematically, if you have strings s₁, s₂, …, sₙ and their respective lengths |s₁|, |s₂|, …, |sₙ|, then the sorted order should satisfy:

$$|s_{i_1}| \leq |s_{i_2}| \leq \cdots \leq |s_{i_n}| $$

where if (|s_{i_k}| = |s_{i_{k+1}}|), the order of s_{i_k} and s_{i_{k+1}} is the same as in the input.

inputFormat

Input is read from standard input (stdin). The first line contains a non-negative integer n, representing the number of strings. Each of the following n lines contains a single string.

outputFormat

Output the sorted list of strings in a single line separated by a single space, written to standard output (stdout).## sample

5
apple
hi
car
hello
a

a hi car apple hello