Vasya 是组织“鼠标和键盘”公共页面的管理员,他的日常职责是发布竞争性编程领域的新闻。对于每条新闻,他还创建了一个主题标签列表,以便更轻松地搜索特定主题。为了解决这个问题,我们将主题标签定义为一个由小写英文字母和位于字符串开头的符号“#”组成的字符串。主题标签的长度定义为其中不包含符号“#”的符号数量。
该页面的首席管理员告诉 Vasya,主题标签应该按字典顺序排列(请查看注释部分的定义)。
Vasya 很懒,所以他不想实际更改已发布新闻中主题标签的顺序。相反,他决定删除一些主题标签的一些后缀(字符串末尾的连续字符)。他可以删除任意数量的字符,甚至可以删除除符号“#”之外的整个字符串。 Vasya 希望选择一种删除后缀的方法,使删除的符号总数尽可能最小。如果有多个最佳解决方案,他可以选择其中任何一个。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 500 000) - 现在正在编辑的主题标签的数量。
接下来的 n 行中的每一行都恰好包含一个正长度的主题标签。
保证所有主题标签的总长度(即除字符“#”之外的字符串总长度)不会超过 500 000。
输出
打印任意最佳解决方案中生成的主题标签。
示例
输入 #1
3 #book #bigtown #big
输出 #1
#b #big #big
输入 #2
3 #book #cool #cold
输出 #2
#book #co #cold
输入 #3
4 #car #cart #art #at
输出 #3
# # #art #at
输入#4
3 #apple #apple #fruit
输出#4
#apple #apple #fruit
注意
如果以下两个条件之一成立,则长度为 m 的单词 a1, a2, ..., am 按字典顺序不大于长度为 k 的单词 b1, b2, ..., bk:
- 在第一个位置 i,使得 ai ≠ bi,字符 ai 在字母表中比字符 bi 更早,即 a 在它们不同的第一个位置比 b 具有更小的字符;
- 如果没有这样的位置 i 并且 m ≤ k,即第一个单词是第二个单词的前缀或者两个单词相等。
如果每个单词(除了最后一个)按字典顺序不大于下一个单词,则称单词序列按字典顺序排序。
对于由小写英文字母组成的单词,词典顺序与词典中的字母词顺序一致。
根据上述定义,如果主题标签由一个字符“#”组成,则按字典顺序,它不大于任何其他有效主题标签。这就是为什么在第三个示例中,我们不能保持前两个主题标签不变并缩短其他两个。