A subsequence of a given sequence is a sequence obtained by deleting zero or more elements from the original sequence. Specifically, if a sequence $X = x_1 x_2 \dots x_m$ is given, another sequence $Z = z_1 z_2 \dots z_k$ is a subsequence of $X$ if there exists a strictly increasing sequence of indices $i_1, i_2, \dots, i_k$ such that for all $j=1, 2, \dots, k$, $z_j = x_{i_j}$. For example, the sequence $Z = \text{GACT}$ is a subsequence of $X = \text{GCTACT}$, with the corresponding increasing sequence of indices being $1, 4, 5, 6$. Given two sequences $X$ and $Y$, a sequence $Z$ is called a common subsequence of $X$ and $Y$ if $Z$ is a subsequence of both $X$ and $Y$. For example, if $X = \text{GCTACT}$ and $Y = \text{GATCCT}$, the sequence $\text{TT}$ is a common subsequence of $X$ and $Y$, and $\text{GACT}$ is also a common subsequence of $X$ and $Y$. Note that for any given sequences $X$ and $Y$, the empty sequence is always a common subsequence of them.

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

Input

The first line contains two positive integers $m$ and $n$ ($1 \le m, n \le 3010$), representing the lengths of the two input sequences $X$ and $Y$, respectively. The next two lines provide the input sequences $X = x_1 x_2 \dots x_m$ and $Y = y_1 y_2 \dots y_n$. Each element in the sequences is one of the 26 English uppercase or lowercase letters. The last line of the file contains a non-negative integer $k$. If $k=1$, it means the result should output all distinct common subsequences of $X$ and $Y$, as well as the total count of distinct common subsequences. If $k=0$, it means the result should only output the total count of distinct common subsequences of $X$ and $Y$.

Output

If $k=1$, first output all distinct common subsequences of $X$ and $Y$, one per line, in lexicographical order. Finally, output the total number of distinct common subsequences. If $k=0$, only output the total number of distinct common subsequences.

Examples

Input 1

6 6
GCTACT
GATCCT
1

Output 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

Input 2

6 6
GCTACT
GATCCT
0

Output 2

26