题目描述

你和 Alice 正在玩单词阶梯谜题。单词阶梯 是一个单词序列，所有单词具有相同的长度，且序列中每个单词与前一个单词仅相差一个字母。

由于你更擅长构造单词阶梯而不是解决它们，你决定为 Alice 设计一个非常具体的谜题。你会给 Alice 一个包含 $n$ 个单词的列表。然后，她将从你的单词列表中构造一个单词阶梯。Alice 必须从列表的第一个单词开始，每次更改一个字母，最终得到列表的最后一个单词。Alice 使用的每个中间单词也必须来自你的单词列表。

Alice 非常擅长解单词阶梯谜题，她总是能构造出最短的单词阶梯。你想迫使 Alice 在她的单词阶梯中使用列表中的 所有 $n$ 个单词。也就是说，利用你单词列表中的单词，从起始单词到结束单词不存在比使用全部 $n$ 个单词更短的单词阶梯。

请构造一个包含 $n$ 个单词的列表，使得从第一个单词到最后一个单词的最短单词阶梯必须使用列表中的所有单词。由于在将谜题交给 Alice 之前你需要验证单词阶梯的解，因此单词列表应按单词阶梯的顺序给出。

输入格式

输入仅一行，包含一个整数 $n$（$3 \le n \le 5{,}000$），表示你需要为 Alice 构造的单词列表（同时也是单词阶梯解）的长度。

输出格式

输出 $n$ 行，每行包含一个长度不超过 $10$ 的单词。所有单词必须互不相同，长度相等，且仅包含小写字母。注意，在本问题中，单词只是小写字母组成的字符串，不必是真正的英文单词。

输出的 $n$ 个单词应按单词阶梯的顺序排列，使得每个单词与前一个单词仅相差一个字母。并且，利用列表中的单词，从第一个单词到最后一个单词不存在使用少于 $n$ 个单词的更短单词阶梯。

可以证明，对于输入范围内的所有 $n$，答案均存在。任何满足上述要求的答案都将被视为正确。

5

lead
load
toad
told
gold

3

aa
ab
bb

提示

翻译由 DeepSeek V3.2 完成