問題文

英大文字および英小文字からなる文字列 $X, Y$ に対して，次の条件をともに満たす場合，その $2$ つの文字列は互いに似て非なる文字列と呼びます．

• $X$ と $Y$ は，英大文字・英小文字の違いを区別しない場合に一致する．
• $X$ と $Y$ で英大文字・英小文字が異なる箇所が，$1$ 文字以上 $K$ 文字以下存在する．

たとえば，$K=2$ のとき，ABC と aBc は，上の条件をともに満たすため，互いに似て非なる文字列です．一方，次の例は互いに似て非なる文字列ではありません．

• ABC と BCD（英大文字・英小文字の違いを区別しなくても一致しない）
• ABC と ABC（英大文字・英小文字が異なる箇所が $0$ 文字である）
• ABC と abc（英大文字・英小文字が異なる箇所が $3$ 文字である）

英大文字・英小文字からなる，長さ $N$ の文字列 $S$ および長さ $M$ の文字列 $T$ が与えられます．

$S$ の（連続する）部分文字列であって，$T$ と互いに似て非なる文字列であるものの個数を求めてください．

ただし，2 つの部分文字列は，文字列として等しい場合でも，取り出す位置が異なれば異なるものとして扱います．（2024/2/9 21:31 追記）

制約

• $N, M, K$ は整数である．
• $1 \leq K \leq M \leq N \leq 5 \times 10^5$
• $S$ は英大文字・英小文字からなる長さ $N$ の文字列である．
• $T$ は英大文字・英小文字からなる長さ $M$ の文字列である．

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$ $K$
$S$
$T$

出力

答えを出力せよ．

サンプル

8 2 1
aiaIAiAI
AI

2

7 3 2
aaaaaaa
AAA

0

15 2 1
DXDXGdXdXgDxDxG
Dx

2