← 返回题目列表

Codeforces · 1915/D

D. 非自然语言处理

中文机器翻译题面 查看原题

Lura 很无聊,决定使用五个字母 $$$\texttt{a}$$$、$$$\texttt{b}$$$、$$$\texttt{c}$$$、$$$\texttt{d}$$$、$$$\texttt{e}$$$ 来创建一种简单的语言。字母有两种类型:

- 元音 - 字母 $$$\texttt{a}$$$ 和 $$$\texttt{e}$$$。它们由 $$$\textsf{V}$$$ 表示。
- 辅音 — 字母 $$$\texttt{b}$$$、$$$\texttt{c}$$$ 和 $$$\texttt{d}$$$。它们由 $$$\textsf{C}$$$ 表示。

语言中的单词是音节序列。卢拉用该语言写下了一个单词,但她不知道如何将其拆分为音节。帮助她把单词分成音节。

例如,给定单词 $$$\texttt{bacedbab}$$$,它将被拆分为音节 $$$\texttt{ba.ced.bab}$$$(点 $$$\texttt{.}$$$ 表示音节边界)。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 单词的长度。

每个测试用例的第二行包含一个由 $$$n$$$ 小写拉丁字符组成的字符串 - 单词。

给出的所有单词都是该语言中的有效单词;也就是说,他们只使用字母$$$\texttt{a}$$$、$$$\texttt{b}$$$、$$$\texttt{c}$$$、$$$\texttt{d}$$$、$$$\texttt{e}$$$,并且每个单词由多个音节组成。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于测试用例,输出一个字符串,表示通过在每对相邻音节之间插入点 $$$\texttt{.}$$$ 来分割成音节的单词。

如果有多个可能的分裂,则输出其中任何一个。输入以至少存在一种可能的分裂的方式给出。

示例

输入 #1

6
8
bacedbab
4
baba
13
daddecabeddad
3
dac
6
dacdac
22
dababbabababbabbababba

输出 #1

ba.ced.bab
ba.ba
dad.de.ca.bed.dad
dac
dac.dac
da.bab.ba.ba.bab.bab.ba.bab.ba