文本生成是人工智能领域的重要任务之一。成功的标准通常基于生成的文本是否与人类编写的文本难以区分。

在本题中，你需要生成看起来像是人类创作的短语。更准确地说，你的程序需要打印 $n$ 个不同的字符串，其中至少 $90\%$ 的字符串必须出现在德语维基百科的文章标题中。具体而言，你打印的字符串中至少有 $90\%$ 需要出现在可从 http://opentrains.mipt.ru/wikinames.dat 获取的文本文件中（该文件通过解压 https://dumps.wikimedia.org/dewiki/20190601/dewiki-20190601-all-titles-in-ns0.gz 获得）。

解压后的文件大小为 $72036684$ 字节，包含 $3828917$ 行。你可以在比赛期间在自己的计算机上下载并分析该文件，但你提交的解决方案不得访问网络。

字符串将按字节进行精确相等性比较。

本题的源代码大小限制为 $100000$ 字节。

输入格式

输入仅包含一行，为一个整数 $n$，$n = 3$（样例）或 $n = 50000$（唯一的非样例情况）。

输出格式

输出 $n$ 行。这些行应当互不相同，且其中至少有 $0.9 \cdot n$ 行（向上取整）需要与上述文本文件中的某一行相等。

样例

样例输入 1

3

样例输出 1

Petrowych
Petrozavodsk
Petrozza