CF777D.Cloud of Hashtags

Vasya is an administrator of a public page of organization "Mouse and keyboard" and his everyday duty is to publish news from the world of competitive programming. For each news he also creates a list of hashtags to make searching for a particular topic more comfortable. For the purpose of this problem we define hashtag as a string consisting of lowercase English letters and exactly one symbol '#' located at the beginning of the string. The length of the hashtag is defined as the number of symbols in it without the symbol '#'.

The head administrator of the page told Vasya that hashtags should go in lexicographical order (take a look at the notes section for the definition).

Vasya is lazy so he doesn't want to actually change the order of hashtags in already published news. Instead, he decided to delete some suffixes (consecutive characters at the end of the string) of some of the hashtags. He is allowed to delete any number of characters, even the whole string except for the symbol '#'. Vasya wants to pick such a way to delete suffixes that the total number of deleted symbols is minimum possible. If there are several optimal solutions, he is fine with any of them.

瓦西里是“鼠标与键盘”组织公共主页的一名管理员，他每天的日常工作是发布来自竞技编程世界的消息。对于每条消息，他还会创建一组标签（hashtag），以便用户能更方便地搜索特定主题。在本题中，我们定义一个标签为一个由小写英文字母组成的字符串，且该字符串开头恰好有一个符号 #。标签的长度定义为该字符串中除 # 以外的字符个数。

主页的总管理员告诉瓦西里：所有标签必须按字典序排列（字典序的定义请参见“注释”部分）。

瓦西里很懒，因此他不想实际更改已发布消息中标签的原有顺序。取而代之，他决定对其中某些标签删除其后缀（即字符串末尾的连续若干字符）。他可以删除任意数量的字符，甚至可以将整个字符串（除开头的 # 外）全部删掉。瓦西里希望选择一种删除后缀的方式，使得被删除的字符总数最小。如果存在多种最优方案，任选其一即可。

The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of hashtags being edited now.

Each of the next n lines contains exactly one hashtag of positive length.

It is guaranteed that the total length of all hashtags (i.e. the total length of the string except for characters '#') won't exceed 500 000.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 500\,000$）——表示当前正在编辑的标签数量。

接下来的 $n$ 行中，每行恰好包含一个长度为正的标签。

保证所有标签的总长度（即所有字符串中除字符 # 外的字符总数）不超过 $500\,000$。

Print the resulting hashtags in any of the optimal solutions.

以任意一种最优解输出最终的标签。

Word _a_1, _a_2, ..., a__m of length m is lexicographically not greater than word _b_1, _b_2, ..., b__k of length k, if one of two conditions hold:

• at first position i, such that a__i ≠ b__i, the character a__i goes earlier in the alphabet than character b__i, i.e. a has smaller character than b in the first position where they differ;
• if there is no such position i and m ≤ k, i.e. the first word is a prefix of the second or two words are equal.

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 consisting of lowercase English letters the lexicographical order coincides with the alphabet word order in the dictionary.

According to the above definition, if a hashtag consisting of one character '#' it is lexicographically not greater than any other valid hashtag. That's why in the third sample we can't keep first two hashtags unchanged and shorten the other two.

长度为 $m$ 的单词 $a_1, a_2, \dots, a_m$ 在字典序上不大于长度为 $k$ 的单词 $b_1, b_2, \dots, b_k$，当且仅当满足以下两个条件之一：

• 在首个满足 $a_i \ne b_i$ 的位置 $i$ 上，字符 $a_i$ 在字母表中位于字符 $b_i$ 之前，即 $a$ 与 $b$ 首次出现差异的位置上，$a$ 的字符比 $b$ 的字符更小；
• 不存在这样的位置 $i$，且 $m \le k$，即第一个单词是第二个单词的前缀，或两个单词完全相等。

若一个单词序列中每个单词（除最后一个外）在字典序上均不大于其后继单词，则称该序列按字典序排序。

对于仅由小写英文字母组成的单词，字典序与词典中的单词字母顺序一致。

根据上述定义，由单个字符 # 构成的标签在字典序上不大于任何其他合法标签。因此，在第三个样例中，我们无法保持前两个标签不变而仅缩短其余两个标签。