← 返回题目列表

Codeforces · 955/D

D. 剪刀

中文机器翻译题面 查看原题

Jenya 最近获得了一个非常有用的工具 - 用于切割字符串的 k 剪刀。它们通常用于从任意字符串 s 中切出长度为 k 的两个不相交的子字符串(为了执行此操作,其长度应至少为 2·k),然后将它们连接起来(保留初始顺序)。例如,在 2-scissors 的帮助下,您可以从 abcde 中剪掉 ab 和 de 并将它们连接成 abde,但不能将 ab 和 bc 连接起来,因为它们是相交的。

在实际使用此工具之前对其进行测试是个好主意。翻阅完论文后,Jenya 得出了两个字符串 s 和 t。他的问题是是否可以将他的剪刀应用于字符串 s,使得生成的连接包含 t 作为子字符串?

输入

第一行包含三个整数n、m、k (2 ≤ m ≤ 2·k ≤ n ≤ 5·105)——分别是s的长度、t的长度以及前面提到的剪刀参数。

接下来两行的 s 和 t 由小写拉丁字母组成。

输出

如果没有答案,请打印“否”。

否则打印“Yes”和两个整数 L 和 R 表示剪切子字符串开始的索引(1 索引)。如果有多个可能的答案,则输出任何一个。

示例

输入 #1

7 4 3
baabaab
aaaa

输出 #1

Yes
1 5

输入 #2

6 3 2
cbcbcb
bcc

输出 #2

Yes
2 5

输入 #3

7 5 3
aabbaaa
aaaaa

输出 #3

No

注意

在第一个示例中,您可以剪切从 1 和 5 开始的两个子字符串。生成的字符串 baaaab 包含 aaaa 作为子字符串。

在第二个示例中,结果字符串是 bccb。