P11999 投入严厉地本地

在本题中，对于一个字符串 $x$，我们定义： - $|x|$ 表示 $x$ 的长度，空字符串长度为 $0$。 - $x_{i \sim j}$ 表示 $x$ 的第 $i$ 个字符到第 $j$ 个字符按顺序连接以后形成的子串，例如 $\texttt{abcd}_{2 \sim 4} = \texttt{bcd}$。 - $y$ 是 $x$ 的前缀当且仅当存在一个 $p$ 满足 $x_{1 \sim p} = y$。 - $y$ 是 $x$ 的后缀当且仅当存在一个 $p$ 满足 $x_{p \sim |x|} = y$。 字符串的字符集是小写字母集合，即字符串仅由小写字母构成。

给定两个字符串 $s, t$，和一个参数 $k$。此外有一个映射规则集合 $f = \{(\lambda_i, \gamma_i) | i = 1,2,3,\dots m\}$。其中 $\lambda_i$ 是长度为 $k$ 的字符串，$\gamma_i$ 是一个长度为 $1$ 的字符串，或一个空字符串，$\lambda_i$ 互不相同，$m$ 是映射规则的数量。 已知对于映射规则集合 $f$，$s$ 可以按如下流程生成字符串 $t$： 1. 令 $i = 1$。 2. 如果 $i > |s|$，生成结束。 3. 如果存在一个 $j \in [1, m]$ 使得 $\lambda_j$ 是 $s_{1 \sim i}$ 的后缀，则令 $t := t \circ \gamma_j$，这里 $:=$ 表示赋值，$\circ$ 表示字符串拼接。 4. 如果对任何的 $j \in [1, m]$ 都有 $\lambda_j$ 不是 $s_{1 \sim i}$ 的后缀，则令 $t:=t \circ s_{i \sim i}$。 5. 令 $i := i + 1$，返回 $2$。 现在，给定 $s$ 和由它生成的字符串 $t$，以及参数 $k$，你需要给出一个映射规则集合 $f$，使得 $s$ 按映射规则 $f$ 生成的字符串是 $t$。

无

无

### 样例 1 解释 第一组数据规则共三条（用 $\epsilon$ 表示空字符串）： - $\texttt{abc} \to \texttt{x}$ - $\texttt{bcd} \to \epsilon$ - $\texttt{cde} \to \texttt{z}$。 过程如下： | $s$ 的前缀 | 匹配规则 | $t$ 的变化 | | :-: | :-: | :-:| | $\texttt{a}$ | |$\texttt{a}$ | $\texttt{ab}$ | | $\texttt{ab}$ | | $\texttt{abc}$ |$\texttt{abc} \to \texttt{x}$| $\texttt{abx}$| | $\texttt{abcd} $ | $\texttt{bcd} \to \epsilon$ | $\texttt{abx}$ | | $\texttt{abcde}$ | $\texttt{cde} \to \texttt{z}$ | $\texttt{abxz}$ | ### 数据规模与约定 - 对 $30\%$ 的数据，保证 $|s| \leq 4$，字符串只有 $\texttt{a},\texttt b$ 两个字符。 - 对 $100\%$ 的数据，保证 $1 \leq T \leq 10$，$1 \leq k \leq |s|$，$1 \leq |t| \leq |s| \leq 7$，$s,t$ 只含小写字母，数据保证存在一个数量小于 $50$ 条的映射规则使得 $s$ 可以按规则映射到 $t$。