Cloud of hashtags
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya leads a public page of organization "Mouse and keyboard" where he every day publishes news from the competitive programming world. He adds a list of hashtags to every news to make searching more comfortable. Let's define hashtag as a string which consists of small English letters and exactly one symbol '#' in the begining of the string. Lenght of hashtag is number of symbols without the symbol '#'.

Vasya's boss said to put hashtags in lexicographical order (to clear look at notes).

You don't want to change the order of hashtags in published news and you decided to delete a suffix (some number of last symbols) from some hashtags. You can delete the all hashtag's text without the symbol '#', but you can't delete this symbol. In many different variants of removal you want to choose one in which you will delete minimum number of symblos. If there are multiple ways to do it, you can output any of them.

Input

The first line of input contains one integer n (1 ≤ n ≤ 500 000) — number of hashtags in news.

Each of next n lines contains exactly one hashtag with positive lenght.

Let's define through L summary lenght of all hashtags. It is guaranteed that in all test L does not exceed 500 000.

Output

Output hashtags which you got after removal of symblos.

Examples

Input
3
#book
#bigtown
#big
Output
#b
#big
#big
Input
3
#book
#cool
#cold
Output
#book
#co
#cold
Input
4
#car
#clothes
#art
#at
Output
#
#
#art
#at
Input
3
#apple
#apple
#fruit
Output
#apple
#apple
#fruit

Note

Word a1, a2, ..., am of length m is lexicographically smaller than word b1, b2, ..., bk of length k, if one of two conditions hold:

The sequence of words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically not greater than the next word.

For the words which consist of small English letters the lexicographical order coincides with the alphabet word order in the vocabulary.