395. String Sorting Challenge

0

Medium

Nishant, a mischievous student in the Launchpad Batch, has jumbled up a set of strings. Your task is to assist Nishant in sorting the strings lexicographically. However, if one string is a complete prefix of another string, the longer string should be placed before the shorter one in the sorted order. For example, if we have the strings 'bat' and 'batman', where 'bat' is a prefix of 'batman', the sorted order should be 'batman' followed by 'bat'.

Input Format

The input consists of an integer N followed by N strings.

Output Format

The output should consist of N lines, each containing one string.

Example

Input

3 bat apple batman

Output

apple batman bat

Constraints

N<=1000
Loading...

View Submissions

Console