Mapping Rule Reconstruction

You are given two strings \(s\) and \(t\), and a positive integer \(k\). In addition, there exists a set of mapping rules \(f = \{(\lambda_i, \gamma_i) \mid i = 1,2,3,\dots, m\}\) where each \(\lambda_i\) is a string of length \(k\) and each \(\gamma_i\) is either a string of length 1 or an empty string. All \(\lambda_i\) are distinct and \(m\) denotes the number of mapping rules.

The string \(t\) is generated from \(s\) based on the following process using the mapping set \(f\):

1. Initialize index \(i = 1\) and result string \(t := \varepsilon\) (empty string).
2. If \(i > |s|\) then terminate the process.
3. If there exists a rule \(j \in [1, m]\) such that \(\lambda_j\) is a suffix of \(s_{1 \sim i}\) (i.e. the prefix of \(s\) of length \(i\)), then update \(t := t \circ \gamma_j\) (here \(\circ\) denotes string concatenation).
4. If for every \(j \in [1, m]\) the string \(\lambda_j\) is not a suffix of \(s_{1 \sim i}\), then update \(t := t \circ s_{i}\) (i.e. append the \(i\)th character of \(s\)).
5. Set \(i := i + 1\) and go back to step 2.

Your task is: Given \(s\), the string \(t\) produced from \(s\) by the above algorithm, and the parameter \(k\), determine a valid mapping rule set \(f\) such that when the above process is applied to \(s\) with \(f\), the resulting string is \(t\).

Note: For positions \(i < k\), note that no mapping rule can be applied because the rule length is \(k\). Therefore, it is necessary that \(s_i = t_i\) for all \(i < k\). For \(i \ge k\), if a mapping rule for the substring \(s_{i-k+1}\dots s_i\) is present in \(f\), then the output character at position \(i\) will be \(\gamma\) from that rule, and if no rule applies then the output is \(s_i\). Once a mapping rule is included for a substring, it applies to every occurrence of that substring as a suffix of \(s_{1 \sim i}\).

inputFormat

The input consists of three lines:

1. The first line contains the string \(s\). (1 ≤ |s| ≤ 10⁵)
2. The second line contains the string \(t\) which is produced from \(s\) by the process described above.
3. The third line contains the integer \(k\) (1 ≤ k ≤ |s|).

It is guaranteed that the input data has at least one valid mapping rule set \(f\).

outputFormat

Output the mapping rule set \(f\) in the following format:

1. In the first line, output an integer \(m\) which is the number of mapping rules in \(f\).
2. Then output \(m\) lines, each line contains two strings separated by a space: the first is \(\lambda_i\) (of length \(k\)), and the second is \(\gamma_i\) (which is either a single character or an empty string). If \(\gamma_i\) is empty, you may output nothing after the space.

The mapping rules must satisfy that when processing \(s\) from \(i=1\) to \(|s|\) using the algorithm, the concatenated output equals \(t\).

sample

abc
abc
2

0