788. String Sort

0

Medium

Nishant is a very naughty boy in Launchpad Batch. One day he was playing with strings, and randomly shuffled them all. Your task is to help Nishant Sort all the strings ( lexicographically ) but if a string is present completely as a prefix in another string, then string with longer length should come first. Eg bat, batman are 2 strings and the string bat is present as a prefix in Batman - then sorted order should have - Batman, bat.

Input Format

N(integer) followed by N strings.

Output Format

N lines each containing one string.

Example

Input

3 bat apple batman

Output

apple batman bat

Constraints

N<=1000
Loading...

View Submissions

Console