题目描述

LZW 压缩是一种非常著名且广泛使用的无损数据压缩算法。

以下是 LZW 压缩算法的流程：

1. 给定一个输入字符串 $S$ 和初始字典$^\dag D$，设字符串 $P$ 为空串。
2. 获取 $S$ 中未被遍历的第一个字符 $c$：
   • 若 $P+c$（加号表示字符串连接）存在于字典中，则令 $P=P+c$，重复执行第 2 步。
   • 否则，将 $P+c$ 添加到字典 $D$，其对应的编码为 $D$ 中元素的个数加一。输出 $P$ 代表的编码，令 $P=c$，重复执行第 2 步。
3. 最后，输出 $P$ 代表的编码。

$\dag$：在本题中，字典 $D$ 是一个结构体数组。其中，每个结构体内存储了两个变量 $S,x$，意为正整数编码 $x$ 可以代表字符串 $S$。

例如，对字符串 ABABABA 进行 LZW 压缩的流程如下：

初始字典 $D$：$\{{\tt A},1\},\{{\tt B},2\}$。

$P$	$c$	$P+c$	$P+c$ 是否在 $D$ 中	输出	新增字典条目	$P$ 更新为
空串	A		是			A
A	B	AB	否	$1$	$\{\texttt{AB},3\}$	B
B	A	BA		$2$	$\{\texttt{BA},4\}$	A
A	B	AB	是			AB
AB	A	ABA	否	$3$	$\{\texttt{ABA},5\}$	A
A	B	AB	是			AB
AB	A	ABA				ABA
ABA	结束			$5$

则 ABABABA 的 LZW 压缩结果为 1 2 3 5。

现给出字符串 $S$ 和初始字典 $D$，请对 $S$ 进行 LZW 压缩，并输出执行完 LZW 压缩后的字典。

输入格式

第一行输入三个整数 $n,k,s$，表示字符串 $S$ 的长度、初始字典 $D$ 的大小，且字符集为前 $s$ 个大写英文字母。

接下来 $k$ 行，每行输入一个字符串，表示字典中的一个条目，输入的第 $i$ 个字符串对应的编号为 $i$。保证前 $s$ 个大写英文字母一定在字典中出现，且这 $s$ 个条目一定是前 $s$ 个给出的。

接下来一行一个字符串 $S$。

输出格式

第一行输出若干个由空格分隔的正整数，表示 $S$ 经 LZW 压缩后的结果。

第二行输出一行一个正整数 $k$，表示字典 $D$ 的大小。

接下来 $k$ 行，每一行输出一个字符串，表示字典 $D$ 的各个条目。你应当按编号从小到大的顺序输出，即你输出的第 $i$ 个字符串对应的编号应为 $i$。

7 2 2
A
B
ABABABA

1 2 3 5
5
A
B
AB
BA
ABA

25 1 1
A
AAAAAAAAAAAAAAAAAAAAAAAAA

1 2 3 4 5 6 4
7
A
AA
AAA
AAAA
AAAAA
AAAAAA
AAAAAAA

19 6 6
A
B
C
D
E
F
ACBECDFCAACBECDACBE

1 3 2 5 3 4 6 3 1 7 9 11 16 5
19
A
B
C
D
E
F
AC
CB
BE
EC
CD
DF
FC
CA
AA
ACB
BEC
CDA
ACBE

提示

样例 1 解释

此样例即为题目描述中的例子。

注意在输出字典的条目时，需要将输入的字典条目一并输出。

样例 2 解释

此样例满足特殊性质 AB。

数据范围与约定

对于全部数据，满足 $1\le n,k\le 3000, 1\le s\le 26$。$D$ 中所有字符串的长度总和不超过 $n$，且 $D$ 中没有重复的字符串。保证前 $s$ 个大写英文字母一定在字典中出现，且这 $s$ 个条目分别使用编码 $1\sim s$。各测试点的详细数据范围见下表。

测试点	$n,k$	特殊性质
$1\sim 3$	$\le 600$	A
$4\sim 7$	$\le 1000$	无
$8\sim 9$	$\le 2000$	B
$10\sim 13$		C
$14\sim 17$		无
$18\sim 20$	$\le 3000$

特殊性质 A：保证 $s=1$。

特殊性质 B：保证 $k=s$。

特殊性质 C：保证字符串 $s$ 为随机生成。