Stable String Sorting by Length

You are given a list of N strings. Your task is to sort these strings in ascending order based on their lengths. If two strings have the same length, their original order (i.e. the order in which they were given) must be preserved. This is a classic example of a stable sort where the relative order of equal elements is maintained.

Formally, given a list \(S = [s_1, s_2, \dots, s_N]\), you need to return a list \(S'\) such that for any two strings \(s_i\) and \(s_j\), if \(|s_i| < |s_j|\) then \(s_i\) appears before \(s_j\) in \(S'\), and if \(|s_i| = |s_j|\) then the order of appearance in \(S'\) is the same as in \(S\).

inputFormat

The first line of input contains an integer N, which indicates the number of strings. The following N lines each contain a single string.

Constraints:

• 0 \(\leq N \leq\) 10⁵ (you can assume reasonable limits for the given problem).
• The strings contain only visible characters and no spaces.

outputFormat

Output the sorted list of strings, one per line, according to their length in ascending order. If two strings have the same length the original order must be preserved.

## sample

4
apple
banana
kiwi
pear

kiwi
pear
apple
banana

</p>