问题陈述

给定 $m$ 个由 A、C、G、T 组成的字符串。让我们在这些字符串中插入空白符号（用 - 表示），使得所有字符串的长度相等，并生成一个 $m \times n$ 的矩阵 S，其中每一行都是一个字符串，$n$ 是字符串的长度。我们将 $S$ 的第 $i$ 行、第 $j$ 列的元素（即字符）表示为 $S_{i,j} (1 \leq i \leq m, 1 \leq j \leq n)$。我们也用 $S_{i,\*}$ 和 $S_{\*,j}$ 分别表示行向量和列向量。让我们考虑在适当的位置插入 -，使得我们可以生成对齐的 $S$，其中每个列向量中都包含相同的字符。为此，我们定义下面的分数 $C$，用于衡量给定的列向量 $t$ 对齐程度有多好。

$C(t) = min_{x \in \{A, T, G, C, -\}} \left| \{ t[i] \; | \; t[i] \neq x \; (i=1, \ldots, m) \} \right|$

$C(t)$ 计算 $t$ 中与在 $t$ 中出现最频繁的字符不相等的字符的数量。例如，当 $t$=CCCC-T 时，C 出现得最频繁，因此与 C 不相等的字符的数量（即 - 和 T）为 $C(t)=2$。当 $t$=CCAA-T 时，可以选择 C 或 A 作为 $x$，因为 C 和 A 的计数相等。如果选择 C 作为 $x$，则 $C(t)$ 变为 $4$，加上 A、- 和 T 的计数。

如果我们能够生成 $S$，使得所有列的 $C(S_{\*,j})$ 之和变得很小，预计给定的 $m$ 个字符串将被很好地对齐。我们称这样的问题为多重对齐，并定义以下分数。

$C_{all}(S) = \sum_{j=1}^n C(S_{\*,j})$

例如，通过在三个字符串 GGATC、GGAT 和 GACC 中插入 - 如下所示进行对齐，

  GGATC
  GGAT-
  G-ACC

得分 $C_{all}(S)$ 变为 $C(S_{\*,1}) + C(S_{\*,2})+ C(S_{\*,3})+ C(S_{\*,4})+ C(S_{\*,5}) = 0 + 1 + 0 + 1 + 1 = 3$。

给定 $m$ 个字符串 $s_{1}$, $\ldots$, $s_{m}$，输出一个多重对齐，使得 $C_{all}(S)$ 尽可能小。

约束条件

• $s_1$,...,$s_m$ 是由 A、C、G、T 组成的字符串。
• 小规模测试用例
  • $8 \leq m \leq 10$。
  • $80 \leq |s_1|, \ldots, |s_m| \leq 100$（字符串的长度用 $|$x$|$ 表示）。
• 大规模测试用例
  • $35 \leq m \leq 50$。
  • $700 \leq |s_1|, \ldots, |s_m| \leq 750$

输入

输入以以下格式从标准输入给出：

$m$ $s_{1}$ $s_{2}$ ： $s_{m}$

输出

以使 $C_{all}$ 尽可能小的顺序输出输入字符串的多重对齐。在每个输入字符串中插入 - 后，它们应按照输入顺序打印。

只有当满足以下条件时，评分系统才会接受用户的输出： - 如果删除 - 后，每行与对应的输入行相等。 - 所有行的长度相等。

示例输入 1

10
GGAGGTTATTGCTGTGGAGGTACTGGAGAAGGAGGATGCTAGCGTTGGGTAAACCACGAGCATTTTGACTTGTACTTCGCCTC
GGGTTATTGCTGTTGTGAGTACTGGAGACAGGAGGGAGTGTTAGAGTTGGGGTAAACCACAGTAGCTCATGTCACTTGGATAACTCGTCAGCCTC
GGTCACTCGCTGTGGAGAGTACTTTGAGACAGGAGGGAGTGCTAGAGTTTGGGGTAAAACCACAGCAGCTCATGCACTTGGATATCTGTGAGCC
GAGGTTAGTGCTGTGGAGAGTACTGGAGACAGGAGGGAGTGCTAGAGTTGGGGTAAAGCACAGCACCATTCACTGATAAATGTCAGGCCTAGGGG
GAGGTATTGCTGTGGAGGGTACTGGAGACAGGAGGAGTGCTAGAGGTTGGGGTAAAACCACAGCAGCTCATTTACTTGATACTGTCAGGCTCAGG
GAGGTTATTTGCTGTGGAGAGTTACTGAGACATGGGGTGCCAAGTTGGGTAGCTACAGCAGCTCATTTCACTTGATACTGCAGGCTCTCAG
GAGTTAATTTCGTGGAGAGTACTAGAGCACAGGAGGGAGGCCAGATTGGGGTATACCACAGCAGCTCGTTCACTTTAACTGTCAGGCCCTCA
ACAGTTTAATTGATGGGCGGAGAGTACTGGAGACAGGAGGGAGTGCTAGAGTGGGGTAAACCACAGCAGCATCTTTCATTATAACTGTCAG
CAAGGTTTTTTCGCTGTGGAGAGTACTGGAGACCGGGGAGTGTAGACTTTGGGGTATCACGTAGCAGCTTATTTCGACTTTGTACTGTAA
GAGTTATTTCTGTGGAGAGAACTGGAG