题目描述

Bajtosia 正在为信息学课程准备一个演示文稿。为此，她必须访问 $n$ 个具有两两不同地址的网站，从中获取所需的信息。

Bajtosia 使用的浏览器有一个文本框，初始时包含空串。通过按键可以修改文本框中的内容，并访问地址等于当前文本框中单词的网站。可用的操作如下：

1. 按键 $\texttt{a}$ 到 $\texttt{z}$ 会在当前单词的末尾追加按下的字母。
2. 按键 $\texttt{BACKSPACE}$ 删除当前单词的最后一个字母（如果当前单词为空串则什么也不做）。
3. 按键 $\texttt{ENTER}$ 会访问地址等于当前单词的网站，然后清空文本框中的单词（即将其变为空串）。
4. 按键 $\texttt{TAB}$ 会将当前单词自动补全为在所有已经访问过的、以当前单词为前缀（即开头片段）的页面中最近一次访问的那一个页面的地址（如果不存在这样的已访问页面，则什么也不做）。

离提交演示文稿的截止时间已经不多了，因此 Bajtosia 想以尽可能少的按键次数访问所有要求访问的网站。Bajtosia 不能访问除要求访问的网站以外的其他网站。Bajtosia 可以以任意顺序访问这些要求访问的网站，并且每个网站必须被访问恰好一次。

请帮助 Bajtosia，求出所需的最小按键次数，以及应该依次按下哪些按键。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示 Bajtosia 需要访问的网站数量。

在接下来的第 $i$ 行（对于 $1 \le i \le n$）中，给出一个非空字符串 $s_i$，由英文小写字母（$\texttt{a}\sim \texttt{z}$）组成，表示第 $i$ 个网站的地址。字符串 $s_i$ 两两不同。

记 $S = |s_1| + \dots + |s_n|$，则有 $S \le 10^6$。

输出格式

输出的第一行应输出一个整数 $k$，表示访问所有给定网站所需的最小按键次数。

输出的第二行应包含一个长度为 $k$ 的按键序列，即为依次按下的按键，从而能够访问所有给定的网站。按键 BACKSPACE、ENTER 和 TAB 分别用字母 B、E 和 T 来表示。

如果存在多个可行解，可以输出其中任意一个。

3
aaaaba
aaaaczzz
aaaadb

21
aaaabaETBBdBETBBczzzE

提示

样例解释

一开始，Bajtosia 逐个字母地在文本框中输入字符串 $\texttt{aaaaba}$，然后按下 $\texttt{ENTER}$。接着她按下 $\texttt{TAB}$，此时文本框中又出现了字符串 $\texttt{aaaaba}$。然后 Bajtosia 连续两次按下 $\texttt{BACKSPACE}$，得到 $\texttt{aaaa}$，再追加两个字母，得到 $\texttt{aaaadb}$，之后按下 $\texttt{ENTER}$。接下来，她按下 $\texttt{TAB}$，再按两次 $\texttt{BACKSPACE}$，再次得到 $\texttt{aaaa}$。最后 Bajtosia 再输入四个字母得到 $\texttt{aaaaczzz}$，并最后一次按下 $\texttt{ENTER}$。

整个过程也在“样例图解”一节的示意图中给出。

大样例

可以在附件中获得大样例。

样例 $\texttt{0a}$ 是题面中展示的样例。此外：

• $\texttt{0b}$：$n = 26$ 个字符串，每个由 $20\,000$ 个字符组成。每个字符串的前 $19\,999$ 个字符都是字母 a，而它们的最后一个字符依次为英文小写字母 a、b、...、z。
• $\texttt{0c}$：$n = 10$ 个字符串，第 $i$ 个字符串（对于 $i = 1, \dots, 10$）由字母 'a' 重复 $18i$ 次组成。
• $\texttt{0d}$：$n = 65534$ 个字符串。输入中包含所有由字母 'a' 和 'b' 组成、长度不超过 $15$ 的非空字符串。
• $\texttt{0e}$：$n = 2$ 个字符串。两个字符串的长度都是 $500\,000$，并且在前 $300\,000$ 个位置上的字母完全相同。在第 $300\,001$ 个位置上的字符二者不同。之后的字符是随机的。

子任务

本题采用捆绑测试。

子任务编号	限制	得分
1	$n \le 8$ 且对所有 $i \in [1..n]$ 均有 $\vert s_i\vert \le 10$	17
2	所有 $s_i$ 的长度相同	12
3	$S \le 1\,000$	32
4	$s_i$ 只由字母 a 和 b 构成	18
5	无额外限制	21

如果你的输出中只有第一行是正确的，你的解法在该测试上将得到该测试分值的 $80\%$。你不必输出第二行也能获得这些分数。

样例图解

在下面的示意图中，给出了上文所述示例测试的一种解法的各个步骤。

::::align{center} ::::