Scissors

题意翻译

给定两个串$s$,$t$和整数$k$,你可以在$s$中取出任意的两个不相交的串,将它们按顺序拼在一起形成一个新串。 求一种取串的方案使得$t$是新串的子串。 ps:k为两个长度为k的不相交的子串

题目描述

Jenya has recently acquired quite a useful tool — $ k $ -scissors for cutting strings. They are generally used for cutting out two non-intersecting substrings of length $ k $ from an arbitrary string $ s $ (its length should be at least $ 2·k $ in order to perform this operation) and concatenating them afterwards (preserving the initial order). For example, with the help of $ 2 $ -scissors you can cut $ ab $ and $ de $ out of $ abcde $ and concatenate them into $ abde $ , but not $ ab $ and $ bc $ since they're intersecting. It's a nice idea to test this tool before using it in practice. After looking through the papers, Jenya came up with two strings $ s $ and $ t $ . His question is whether it is possible to apply his scissors to string $ s $ such that the resulting concatenation contains $ t $ as a substring?

输入输出格式

输入格式


The first line contains three integers $ n $ , $ m $ , $ k $ $ (2<=m<=2·k<=n<=5·10^{5}) $ — length of $ s $ , length of $ t $ and the aforementioned scissors' parameter correspondingly. The next two lines feature $ s $ and $ t $ consisting of lowercase latin letters.

输出格式


If there is no answer, print «No». Otherwise print «Yes» and two integers $ L $ and $ R $ denoting the indexes where cutted substrings start ( $ 1 $ -indexed). If there are several possible answers, output any.

输入输出样例

输入样例 #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

说明

In the first sample case you can cut out two substrings starting at $ 1 $ and $ 5 $ . The resulting string baaaab contains aaaa as a substring. In the second sample case the resulting string is bccb.