Leonid works for a small and promising start-up that works on decoding the human genome. His duties include solving complex problems of finding certain patterns in long strings consisting of letters 'A', 'T', 'G' and 'C'.

Let's consider the following scenario. There is a fragment of a human DNA chain, recorded as a string S. To analyze the fragment, you need to find all occurrences of string T in a string S. However, the matter is complicated by the fact that the original chain fragment could contain minor mutations, which, however, complicate the task of finding a fragment. Leonid proposed the following approach to solve this problem.

Let's write down integer k ≥ 0 — the error threshold. We will say that string T occurs in string S on position i (1 ≤ i ≤ |S| - |T| + 1), if after putting string T along with this position, each character of string T corresponds to the some character of the same value in string S at the distance of at most k. More formally, for any j (1 ≤ j ≤ |T|) there must exist such p (1 ≤ p ≤ |S|), that |(i + j - 1) - p| ≤ k and S[p] = T[j].

For example, corresponding to the given definition, string "ACAT" occurs in string "AGCAATTCAT" in positions 2, 3 and 6.

<image>

Note that at k = 0 the given definition transforms to a simple definition of the occurrence of a string in a string.

Help Leonid by calculating in how many positions the given string T occurs in the given string S with the given error threshold.

Input

The first line contains three integers |S|, |T|, k (1 ≤ |T| ≤ |S| ≤ 200 000, 0 ≤ k ≤ 200 000) — the lengths of strings S and T and the error threshold.

The second line contains string S.

The third line contains string T.

Both strings consist only of uppercase letters 'A', 'T', 'G' and 'C'.

Output

Print a single number — the number of occurrences of T in S with the error threshold k by the given definition.

Examples

Input

10 4 1
AGCAATTCAT
ACAT


Output

3

Note

If you happen to know about the structure of the human genome a little more than the author of the problem, and you are not impressed with Leonid's original approach, do not take everything described above seriously.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
double PI = 2.0 * acos(0.0);
struct FftTables {
  int n;
  int *bit_reversed;
  double *trig_tables;
};
static double accurate_sine(int i, int n);
static int floor_log2(int n);
static int reverse_bits(int x, int n);
void *fft_init(size_t n) {
  if (n < 4 || n > UINT64_MAX || (n & (n - 1)) != 0) return NULL;
  if (n - 4 > SIZE_MAX / sizeof(double) / 2 || n > SIZE_MAX / sizeof(size_t))
    return NULL;
  struct FftTables *tables = new FftTables();
  if (tables == NULL) return NULL;
  tables->n = n;
  tables->bit_reversed = new int[n];
  tables->trig_tables = new double[2 * n + 1];
  if (tables->bit_reversed == NULL || tables->trig_tables == NULL) {
    free(tables->bit_reversed);
    free(tables->trig_tables);
    free(tables);
    return NULL;
  }
  int levels = floor_log2(n);
  for (int i = 0; i < n; i++) tables->bit_reversed[i] = reverse_bits(i, levels);
  int k = 0;
  for (int size = 8; size <= n; size *= 2) {
    for (int i = 0; i < size / 2; i += 4) {
      for (int j = 0; j < 4; j++, k++) {
        tables->trig_tables[k] = accurate_sine(i + j + size / 4, size);
      }
      for (int j = 0; j < 4; j++, k++) {
        tables->trig_tables[k] = accurate_sine(i + j, size);
      }
    }
    if (size == n) break;
  }
  return tables;
}
void fft_destroy(void *tables) {
  if (tables == NULL) return;
  struct FftTables *tbl = (struct FftTables *)tables;
  free(tbl->bit_reversed);
  free(tbl->trig_tables);
  memset(tbl, 0, sizeof(struct FftTables));
  free(tbl);
}
static double accurate_sine(int i, int n) {
  if (n % 4 != 0)
    return NAN;
  else {
    int neg = 0;
    i %= n;
    if (i >= n / 2) {
      neg = 1;
      i -= n / 2;
    }
    if (i >= n / 4) i = n / 2 - i;
    double val;
    if (i * 8 < n)
      val = sin(2 * PI * i / n);
    else
      val = cos(2 * PI * (n / 4 - i) / n);
    return neg ? -val : val;
  }
}
static int floor_log2(int n) {
  int result = 0;
  for (; n > 1; n /= 2) result++;
  return result;
}
static int reverse_bits(int x, int n) {
  int result = 0;
  for (int i = 0; i < n; i++, x >>= 1) {
    result = (result << 1) | (x & 1);
  }
  return result;
}
const int K = 19;
double _r[1 << K], _i[1 << K];
void fft_transform(const void *tables) {
  const struct FftTables *tbl = (const struct FftTables *)tables;
  int n = tbl->n;
  const int *bitreversed = tbl->bit_reversed;
  for (int i = 0; i < n; i++) {
    int j = bitreversed[i];
    if (i < j) {
      double tp0re = _r[i];
      double tp0im = _i[i];
      double tp1re = _r[j];
      double tp1im = _i[j];
      _r[i] = tp1re;
      _i[i] = tp1im;
      _r[j] = tp0re;
      _i[j] = tp0im;
    }
  }
  if (n >= 2) {
    for (int i = 0; i < n; i += 2) {
      double tpre = _r[i];
      double tpim = _i[i];
      _r[i] += _r[i + 1];
      _i[i] += _i[i + 1];
      _r[i + 1] = tpre - _r[i + 1];
      _i[i + 1] = tpim - _i[i + 1];
    }
  }
  if (n >= 4) {
    for (int i = 0; i < n; i += 4) {
      double tpre, tpim;
      tpre = _r[i];
      tpim = _i[i];
      _r[i] += _r[i + 2];
      _i[i] += _i[i + 2];
      _r[i + 2] = tpre - _r[i + 2];
      _i[i + 2] = tpim - _i[i + 2];
      tpre = _r[i + 1];
      tpim = _i[i + 1];
      _r[i + 1] += _i[i + 3];
      _i[i + 1] -= _r[i + 3];
      tpre -= _i[i + 3];
      tpim += _r[i + 3];
      _r[i + 3] = tpre;
      _i[i + 3] = tpim;
    }
  }
  const double *trigtables = tbl->trig_tables;
  for (int size = 8; size <= n; size <<= 1) {
    int halfsize = size >> 1;
    for (int i = 0; i < n; i += size) {
      for (int j = 0, off = 0; j < halfsize; j += 4, off += 8) {
        for (int k = 0; k < 4; k++) {
          int vi = i + j + k;
          int ti = off + k;
          double re = _r[vi + halfsize];
          double im = _i[vi + halfsize];
          double tpre = re * trigtables[ti] + im * trigtables[ti + 4];
          double tpim = im * trigtables[ti] - re * trigtables[ti + 4];
          _r[vi + halfsize] = _r[vi] - tpre;
          _i[vi + halfsize] = _i[vi] - tpim;
          _r[vi] += tpre;
          _i[vi] += tpim;
        }
      }
    }
    if (size == n) break;
    trigtables += size;
  }
}
struct base {
  double x, y;
  base() { x = y = 0; }
  base(double _x, double _y) { x = _x, y = _y; }
  base(double _x) { x = _x, y = 0; }
  void operator=(double _x) { x = _x, y = 0; }
  double real() { return x; }
  double imag() { return y; }
  base operator+(const base &b) { return base(x + b.x, y + b.y); }
  void operator+=(const base &b) { x += b.x, y += b.y; }
  base operator*(const base &b) {
    return base(x * b.x - y * b.y, x * b.y + y * b.x);
  }
  void operator*=(const base &b) {
    double p = x * b.x - y * b.y, q = x * b.y + y * b.x;
    x = p, y = q;
  }
  void operator/=(double k) { x /= k, y /= k; }
  base operator-(const base &b) { return base(x - b.x, y - b.y); }
  void operator-=(const base &b) { x -= b.x, y -= b.y; }
  base conj() { return base(x, -y); }
};
void *tables[K + 1];
void precompute_tables() {
  for (int i = 2; i <= K; i++) tables[i] = fft_init(1 << i);
}
unsigned long long temp[1 << K];
vector<int> naive_mul(vector<int> &a, vector<int> &b) {
  int sz = a.size() + b.size() - 1;
  vector<int> c(sz);
  for (int i = 0; i < a.size(); i++)
    for (int j = 0; j < b.size(); j++) c[i + j] += a[i] * (long long)b[j];
  return c;
}
void fft(vector<base> &a, bool invert) {
  int n = a.size();
  for (int i = 0; i < n; i++) {
    _r[i] = a[i].x, _i[i] = a[i].y;
  }
  int m = floor_log2(n);
  if (!tables[m]) tables[m] = fft_init(n);
  fft_transform(tables[m]);
  a[0] = base(_r[0], _i[0]);
  for (int i = 1; i < n; i++) {
    a[i] = base(_r[invert ? n - i : i], _i[invert ? n - i : i]);
  }
  if (invert)
    for (int i = 0; i < n; ++i) a[i] /= n;
}
void mul(vector<int> &a, vector<int> b) {
  int sza = a.size();
  int szb = b.size();
  int fsz = sza + szb - 1;
  int n = 1;
  while (n < fsz) n <<= 1;
  vector<base> fa(n);
  for (int i = 0; i < sza; i++) fa[i] += base(a[i]);
  for (int i = 0; i < szb; i++) fa[i] += base(0, 1) * base(b[i]);
  fft(fa, false);
  for (int i = 0; i <= (n >> 1); ++i) {
    base p = fa[i] + fa[(n - i) % n].conj();
    base q = fa[i] - fa[(n - i) % n].conj();
    fa[i] = (p * q * base(0, -0.25));
    if (i > 0) fa[(n - i)] = fa[i].conj();
  }
  fft(fa, true);
  a.resize(fsz);
  for (int i = 0; i < fsz; i++) a[i] = ((long long)(fa[i].real() + 0.5));
}
const int N = 200005;
char S[N], T[N];
int cnt[N], pref[4][N], b[N];
vector<int> v1, v2;
int val(char c) {
  if (c == 'A') return 1;
  if (c == 'T') return 0;
  if (c == 'C') return 2;
  if (c == 'G') return 3;
}
int main() {
  int n, m, k;
  scanf("%d", &(n));
  scanf("%d", &(m));
  scanf("%d", &(k));
  v1.resize(n + 1);
  v2.resize(n + 1);
  scanf("%s ", S);
  scanf("%s", T);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 4; j++) pref[j][i] = pref[j][i - 1];
    pref[val(S[i - 1])][i]++;
  }
  for (int j = 0; j < 4; j++) {
    v1.clear();
    v1.resize(n + 1);
    for (int i = 0; i < m; i++) v1[i] = (val(T[i]) == j);
    for (int i = 1; i <= n; i++) {
      int lo = i - k, hi = i + k;
      v2[n + 1 - i] = (pref[j][min(hi, n)] > pref[j][max(0, lo - 1)]);
    }
    mul(v1, v2);
    for (int i = 1; i <= n; i++) cnt[i] += v1[i];
  }
  int ans = 0;
  for (int i = 1; i <= n; i++)
    if (cnt[i] == m) ans++;
  cout << ans << endl;
}
