F: 部分文字列分解

問題

2 つの文字列 S と T および整数 k が与えられる。 T の長さ k 以上の連続する部分文字列を考えたとき、それらの連結で S を構成できるか判定せよ。

ここで文字列 s = s_1 s_2 ... s_n の連続する部分文字列 s[l, r] = s_l s_{l+1} ... s_r (1 \leq l \leq r \leq n) とは、s の l 文字目から r 文字目までを切り出してできる文字列を指し、その長さは r - l + 1 である。

入力形式

S
T
k

制約

• S と T は小文字アルファベットからなる
• 1 \leq |S|, |T| \leq 2\times 10^5
• 1 \leq k \leq |T|

出力形式

S を構成できるとき Yes を、そうでないとき No を一行に出力せよ。

入力例1

abracadabra
cadabra
4

出力例1

Yes

T の長さ 4 以上の部分文字列である abra と cadabra を連結させることで abracadabra が構成でき、これは S と等しい文字列である。

入力例2

abcd
zcba
1

出力例2

No

入力例3

abc
zcba
1

出力例3

Yes

入力例4

abcdefg
abcddefg
4

出力例4

No