CF955D Scissors

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?

N/A

N/A

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.