T195761 马吃

idea & data：[zrmpaul](/user/226760) tester：[绝顶我为峰](/user/85682) & [Hilarious_Reality](/user/80049) 感谢@[cmll02](/user/171487) 贡献了一组 Hack 数据，该组数据不计入得分。 ------- - 本题中「**子串**」的定义如下： 字符串 $S$ 的子串是 $S$ 中**连续**的任意个字符组成的字符串。$S$ 的子串可用起始位置 $l$ 与终止位置 $r$ 来表示，记为 $S_{l,r}(1 \leq l \leq r \leq |S|)$，$ |S|$ 表示 $S$ 的长度。 - 本题中「**一一对应**」的定义如下: 如果映射 $f$ 是集合 $A$ 到集合 $B$ 的映射，并且对于集合 $B$ 中的元素，在集合 $A$ 中**有且只有**一个原象，则这两个元素之间存在一一对应关系。例如 $\texttt{a}\to \texttt{b},\texttt{c}\to\texttt{d}$ 是一一对应的，但 $\texttt{a}\to\texttt{c},\texttt{b}\to\texttt{c}$ 或者 $\texttt{a}\to\texttt{b},\texttt{a}\to\texttt{c}$ 都不是一一对应的。

给定两个字符串 $A$ 和 $B$。$A$ 的长度为 $n$，$B$ 的长度为 $m$。 求出 $A$ 对应后的字符串 $A'$，使得 $B$ 是 $A'$ 的一个子串。$A$ 中的每个字母与 $A'$ 中每个字母要**一一对应**。 例如：假设字符对应关系为 $\texttt{a}\to \texttt{b}$，$\texttt{b}\to \texttt{c}$，$\texttt{c}\to \texttt{a}$，$A$ 为 $\texttt{bca}$，则 $A'$ 为 $\texttt{cab}$。 输出 $A'$。若无解则输出 `-1`。

第一行，两个正整数： $n,m$，表示字符串 $A,B$ 的长度。 第二行，一个字符串 $A$。 第三行，一个字符串 $B$。

共一行，若有解则输出 $A'$，无解则输出 `-1`。

### 数据范围 **本题采用捆绑测试。** | Subtask | 分数 | $1\le n,m\le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | 1 | $6$ | $2\times10^5$ | $n < m$ | | 2 | $28$ | $2\times10^3$ | 无 | | 3 | $8$ | $2\times10^5$ | 保证 $A,B$ 只由 $\texttt{a,b}$ 构成 | | 4 | $28$ | $5\times10^4$ | 无 | | 5 | $30$ | $2\times10^5$ | 无 | 对于 $100\%$ 的数据，$1 \le n,m \le 2\times10^5$。保证 $A,B$ 只包括 $26$ 个小写英文字母。