印章

题目描述

给定一个由大写英文字母组成的长度为 $N$ 的字符串 $S$,以及一个由大写英文字母组成的长度为 $M\ (\le N)$ 的字符串 $T$。

有一个只由 # 组成的长度为 $N$ 的字符串 $X$。判断能否通过进行以下操作任意次,使 $X$ 与 $S$ 一致:

• 从 $X$ 中选出连续的 $M$ 个字符,用 $T$ 替换。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$S$
$T$

输出格式

若能使 $X$ 与 $S$ 一致,输出 Yes,否则输出 No。

样例

7 3
ABCBABC
ABC

Yes

下面,用 $X[l:r]$ 表示 $X$ 的第 $l$ 个字符到第 $r$ 个字符之间的部分。

按如下方式操作可以使 $X$ 与 $S$ 一致:

1. 将 $X[3:5]$ 用 $T$ 替换。$X$ 变成 ##ABC##。
2. 将 $X[1:3]$ 用 $T$ 替换。$X$ 变成 ABCBC##。
3. 将 $X[5:7]$ 用 $T$ 替换。$X$ 变成 ABCBABC。

7 3
ABBCABC
ABC

No

无论怎样操作,都无法使 $X$ 与 $S$ 一致。

12 2
XYXXYXXYYYXY
XY

Yes

数据范围

• $1 \le N \le 2\times 10^5$
• $1 \le M \le \min(N, 5)$
• $S$ 是由大写英文字母组成的长度为 $N$ 的字符串
• $T$ 是由大写英文字母组成的长度为 $M$ 的字符串