Description

A subsequence of a given sequence is obtained by deleting some elements from that sequence. Precisely, given a sequence $X = x_1 x_2 \ldots x_m$, another sequence $Z = z_1 z_2 \ldots z_k$ is a subsequence of $X$ if there exists a strictly increasing index sequence $i_1, i_2, \ldots, i_k$ such that for all $j = 1, 2, \ldots, k$ we have $z_j = x_{i_j}$.

For example, the sequence $Z = ``GACT''$ is a subsequence of the sequence $X = ``GCTACT''$, with the corresponding increasing index sequence $1, 4, 5, 6$. Given two sequences $X$ and $Y$, when another sequence $Z$ is a subsequence of both $X$ and $Y$, we call $Z$ a common subsequence of $X$ and $Y$. For example, if $X = ``GCTACT''$ and $Y = ``GATCCT''$, the sequence T'' is a common subsequence of $X$ and $Y$, and the sequence GACT'' is also a common subsequence of $X$ and $Y$. Note that for any given sequences $X$ and $Y$, the empty sequence is always their common subsequence.

The All Common Subsequences problem asks you, given two sequences $X = x_1 x_2 \ldots x_m$ and $Y = y_1 y_2 \ldots y_n$, to find all distinct common subsequences of $X$ and $Y$.

Input Format

The first line contains two positive integers $m$ and $n$, the lengths of the two input sequences $X$ and $Y$.

The next two lines give the input sequences $X = x_1 x_2 \cdots x_m$ and $Y = y_1 y_2 \cdots y_n$, where each element of a sequence is an English letter, uppercase or lowercase.

The last line contains a non-negative integer $k$.

If $k = 1$, you must output all distinct common subsequences of $X$ and $Y$, and also how many distinct common subsequences $X$ and $Y$ have.

If $k = 0$, you must output only how many distinct common subsequences $X$ and $Y$ have.

Output Format

Output all distinct common subsequences of $X$ and $Y$, or output how many distinct common subsequences $X$ and $Y$ have. When $k = 1$, first output all distinct common subsequences of $X$ and $Y$, one per line, in ascending lexicographic order. Finally, output the number of distinct common subsequences. When $k = 0$, output only the number of distinct common subsequences.

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

Hint

$1 \leq m, n \leq 3010$.

The answer can be very large.

Translated by ChatGPT 5