English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
Print the resulting hashtags in any of the optimal solutions.
[samples]
## Note
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.
Vasya 是组织 "Mouse and keyboard" 公共页面的管理员，他的日常职责是发布竞技编程领域的新闻。对于每条新闻，他都会创建一组标签，以便更方便地搜索特定主题。在本题中，我们将标签定义为一个由小写英文字母组成、且恰好包含一个位于字符串开头的 "_#_" 符号的字符串。标签的 _长度_ 定义为其中符号 "_#_" 之外的字符数量。
页面的首席管理员告诉 Vasya，标签应按字典序排列（详见注释部分的定义）。
Vasya 很懒，他不想实际更改已发布新闻中标签的顺序。相反，他决定删除某些标签的后缀（字符串末尾的连续字符）。他可以删除任意数量的字符，甚至可以删除除 "_#_" 之外的所有字符。Vasya 希望选择一种删除后缀的方式，使得删除的字符总数 _最小_。如果有多个最优解，他可以接受其中任意一个。
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 500 000]）—— 当前正在编辑的标签数量。
接下来的 #cf_span[n] 行，每行包含一个长度为正数的标签。
保证所有标签的总长度（即所有字符串中除去 "_#_" 字符后的总长度）不超过 #cf_span[500 000]。
请输出任意一种最优解下的结果标签。
长度为 #cf_span[m] 的单词 #cf_span[a1, a2, ..., am] 被称为 _字典序不大于_ 长度为 #cf_span[k] 的单词 #cf_span[b1, b2, ..., bk]，当且仅当满足以下两个条件之一：
在第一个满足 #cf_span[ai ≠ bi] 的位置 #cf_span[i]，字符 #cf_span[ai] 在字母表中位于 #cf_span[bi] 之前，即在第一个不同的位置，#cf_span[ai] 的字符小于 #cf_span[bi]；
若不存在这样的位置 #cf_span[i]，且 #cf_span[m ≤ k]，即第一个单词是第二个单词的前缀，或两个单词完全相等。
若一个单词序列中，每个单词（除了最后一个）都字典序不大于下一个单词，则称该序列按字典序排序。
对于由小写英文字母组成的单词，字典序与字典中的字母顺序一致。
根据上述定义，仅由一个字符 "_#_" 组成的标签，字典序不大于任何其他合法标签。因此，在第三个样例中，我们不能保持前两个标签不变而仅缩短后两个。
## Input
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 500 000]）—— 当前正在编辑的标签数量。接下来的 #cf_span[n] 行，每行包含一个长度为正数的标签。保证所有标签的总长度（即所有字符串中除去 "_#_" 字符后的总长度）不超过 #cf_span[500 000]。
## Output
请输出任意一种最优解下的结果标签。
[samples]
## Note
长度为 #cf_span[m] 的单词 #cf_span[a1, a2, ..., am] 被称为 _字典序不大于_ 长度为 #cf_span[k] 的单词 #cf_span[b1, b2, ..., bk]，当且仅当满足以下两个条件之一：在第一个满足 #cf_span[ai ≠ bi] 的位置 #cf_span[i]，字符 #cf_span[ai] 在字母表中位于 #cf_span[bi] 之前，即在第一个不同的位置，#cf_span[ai] 的字符小于 #cf_span[bi]；若不存在这样的位置 #cf_span[i]，且 #cf_span[m ≤ k]，即第一个单词是第二个单词的前缀，或两个单词完全相等。若一个单词序列中，每个单词（除了最后一个）都字典序不大于下一个单词，则称该序列按字典序排序。对于由小写英文字母组成的单词，字典序与字典中的字母顺序一致。根据上述定义，仅由一个字符 "_#_" 组成的标签，字典序不大于任何其他合法标签。因此，在第三个样例中，我们不能保持前两个标签不变而仅缩短后两个。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of hashtags.
For each $ i \in \{1, \dots, n\} $, let $ h_i $ be the $ i $-th hashtag, represented as $ h_i = \texttt{\#} + s_i $, where $ s_i \in \Sigma^* $ is a string of lowercase English letters (possibly empty), and $ \Sigma = \{a, b, \dots, z\} $.
Let $ \ell_i = |s_i| $ be the length of the suffix (without `#`).
**Constraints**
1. $ 1 \leq n \leq 500{,}000 $
2. $ \sum_{i=1}^n \ell_i \leq 500{,}000 $
**Objective**
Find strings $ s_i' \in \Sigma^* $ such that $ s_i' $ is a prefix of $ s_i $ for each $ i $, and the sequence $ \texttt{\#} + s_1', \texttt{\#} + s_2', \dots, \texttt{\#} + s_n' $ is lexicographically non-decreasing, while minimizing the total number of deleted characters:
$$
\sum_{i=1}^n (\ell_i - |s_i'|)
$$
Output $ \texttt{\#} + s_i' $ for each $ i $.
API Response (JSON)
{
"problem": {
"name": "D. Cloud of Hashtags",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF777D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vasya 是组织 \"Mouse and keyboard\" 公共页面的管理员，他的日常职责是发布竞技编程领域的新闻。对于每条新闻，他都会创建一组标签，以便更方便地搜索特定主题。在本题中，我们将标签定义为一个由小写英文字母组成、且恰好包含一个位于字符串开头的 \"_#_\" 符号的字符串。标签的 _长度_ 定义为其中符号 \"_#_\" 之外的字符数量。\n\n页面的首席管理员告诉 Vasya，标签应按字典序...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of hashtags. \nFor each $ i \\in \\{1, \\dots, n\\} $, let $ h_i $ be the $ i $-th hashtag, represented as $ h_i = \\texttt{\\#} + s_i $, where $ s...",
"is_translate": false,
"language": "Formal"
}
]
}