题目描述

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 $X=x_1x_2\ldots x_m$，则另一序列 $Z=z_1z_2\ldots z_k$ 是 $X$ 的子序列是指存在一个严格递增下标序列 $i_1,i_2, \ldots ,i_k$ 使得对于所有 $j=1,2,…,k$ 有 $z_j=x_{i_j}$。

例如，序列 $Z=$GACT 是序列 $X=$GCTACT 的子序列，相应的递增下标序列为 $1,4,5,6$。给定两个序列 $X$ 和 $Y$，当另一序列 $Z$ 既是 $X$ 的子序列又是 $Y$ 的子序列时，称 $Z$ 是序列 $X$ 和 $Y$ 的公共子序列。例如，若 $X=$GCTACT， $Y=$GATCCT，序列 $T$ 是 $X$ 和 $Y$ 的一个公共子序列，序列 GACT 也是 $X$ 和 $Y$ 的一个公共子序列。注意对于任何给定的序列 $X$ 和 $Y$，空序列总是它们的一个公共子序列。

所有公共子序列问题是要求对于给定的 $2$ 个序列 $X=x_1x_2\ldots x_m$ 和 $Y=y_1y_2\ldots y_m$，找出 $X$ 和 $Y$ 的所有不同的公共子序列。

输入格式

文件的第一行有两个正整数 $m$ 和 $n$，分别表示 $2$ 个输入序列 $X$ 和 $Y$ 的长度。

接下来的两行分别给出输入序列 $X=x_1x_2\cdots x_m$ 和 $Y=y_1y_2\cdots y_m$，其中序列中每个元素均为二十六个英文大小写字母。

文件的最后一行给出一个非负整数 $k$。

$k$ 的值为 $1$ 时，表示计算结果要输出 $X$ 和 $Y$ 的所有不同的公共子序列，以及 $X$ 和 $Y$ 有多少个不同的公共子序列。

$k$ 的值为 $0$ 时，表示计算结果只要输出 $X$ 和 $Y$ 有多少个不同的公共子序列。

输出格式

将计算出的 $X$ 和 $Y$ 的所有不同的公共子序列，或 $X$ 和 $Y$ 有多少个不同的公共子序列输出到文件中。当 $k=1$ 时，先输出 $X$ 和 $Y$ 的所有不同的公共子序列，每行输出一个公共子序列，按字典序从小到大输出。最后输出不同的公共子序列的个数。当 $k=0$ 时，只要输出不同的公共子序列的个数。

6 6
GCTACT
GATCCT 1

A
AC
ACT
AT 
C  
CC 
CCT
CT 
G  
GA 
GAC
GACT
GAT 
GC  
GCC 
GCCT
GCT 
GT  
GTC 
GTCT
GTT 
T   
TC  
TCT 
TT  
26

提示

$1 \leq m,n \leq 3010$

答案....很大啦