Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Scissors

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJenya 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?

Input

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.

Output

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.

Examples

Input

7 4 3

baabaab

aaaa

Output

Yes

1 5

Input

6 3 2

cbcbcb

bcc

Output

Yes

2 5

Input

7 5 3

aabbaaa

aaaaa

Output

No

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2018 04:54:01 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|