AT_nikkei2019ex_a Prefix Array

给定一个字符串 $S$。请你求出 $S$ 的 *前缀数组*。 这里，前缀数组是指，将 [后缀数组](https://ja.wikipedia.org/wiki/%E6%8E%A5%E5%B0%BE%E8%BE%9E%E9%85%8D%E5%88%97)（链接为维基百科“接尾辞配列”）定义中的“后缀”替换为“前缀”后得到的数组。 （具体例子可参见下方的样例 1。）

输入为以下格式，从标准输入读取。 > $S$

请输出 $S$ 的前缀数组，共 $|S|$ 行。

## 限制条件 - $1 \leq |S| \leq 100,\!000$ - $S$ 仅由小写英文字母组成。 ## 样例解释 1 将 `chokudai` 的所有前缀按字典序排序后如下： - `c` - `ch` - `cho` - `chok` - `choku` - `chokud` - `chokuda` - `chokudai` 由 ChatGPT 4.1 翻译