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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DFuzzySearch solver = new DFuzzySearch();
        solver.solve(1, in, out);
        out.close();
    }

    static class DFuzzySearch {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int s = in.scanInt();
            int t = in.scanInt();
            int k = in.scanInt();
            char[] ar = in.scanString().toCharArray();
            char[] br = in.scanString().toCharArray();
            boolean[] arr = new boolean[s];
            Arrays.fill(arr, t - 1, s, true);
            for (char c : "AGCT".toCharArray()) {
                long[] pre = new long[s + 1];
                for (int i = 0; i < s; i++) {
                    if (ar[i] == c) {
                        pre[Math.max(0, i - k)]++;
                        pre[Math.min(i + k + 1, s)]--;
                    }
                }
                for (int i = 1; i < s; i++) pre[i] += pre[i - 1];
                for (int i = 0; i < s; i++) if (pre[i] > 0) pre[i] = 1;
                long[] another = new long[t];
                int count = 0;
                for (int i = 0; i < t; i++) {
                    if (br[i] == c) {
                        another[t - i - 1] = 1;
                        count++;
                    }
                }
                if (count == 0) continue;
                long[] multiplication = FFT.convolute(another, pre);
                for (int i = t - 1; i < s; i++) {
                    if (multiplication[i] != count) arr[i] = false;
                }
            }
            int ans = 0;
            for (int i = t - 1; i < s; i++) if (arr[i]) ans++;
            out.println(ans);
        }

    }

    static class CodeHash {
        public static long pow(long a, long b, long m) {
            long res = 1;
            a %= m;
            while (b > 0) {
                if ((b & 1) == 1) res = (res * a) % m;
                a = (a * a) % m;
                b >>= 1;
            }
            return res;
        }

    }

    static class FFT {
        public static final int[] NTTPrimes = {1053818881, 1051721729, 1045430273, 1012924417, 1007681537, 1004535809, 998244353, 985661441, 976224257, 975175681};
        public static final int[] NTTPrimitiveRoots = {7, 6, 3, 5, 3, 3, 3, 3, 3, 17};

        private static long[] garnerPrepare(int[] m) {
            int n = m.length;
            assert n == m.length;
            if (n == 0) return new long[0];
            long[] gamma = new long[n];
            for (int k = 1; k < n; k++) {
                long prod = 1;
                for (int i = 0; i < k; i++) {
                    prod = prod * m[i] % m[k];
                }
                gamma[k] = invl(prod, m[k]);
            }
            return gamma;
        }

        public static long[] convolute(long[] a, long[] b) {
            int USE = 2;
            int m = Math.max(2, Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2);
            long[][] fs = new long[USE][];
            for (int k = 0; k < USE; k++) {
                int P = NTTPrimes[k], g = NTTPrimitiveRoots[k];
                long[] fa = nttmb(a, m, false, P, g);
                long[] fb = a == b ? fa : nttmb(b, m, false, P, g);
                for (int i = 0; i < m; i++) {
                    fa[i] = fa[i] * fb[i] % P;
                }
                fs[k] = nttmb(fa, m, true, P, g);
            }

            int[] mods = Arrays.copyOf(NTTPrimes, USE);
            long[] gammas = garnerPrepare(mods);
            int[] buf = new int[USE];
            for (int i = 0; i < fs[0].length; i++) {
                for (int j = 0; j < USE; j++) buf[j] = (int) fs[j][i];
                long[] res = garnerBatch(buf, mods, gammas);
                long ret = 0;
                for (int j = res.length - 1; j >= 0; j--) ret = ret * mods[j] + res[j];
                fs[0][i] = ret;
            }
            return fs[0];
        }

        private static long[] garnerBatch(int[] u, int[] m, long[] gamma) {
            int n = u.length;
            assert n == m.length;
            long[] v = new long[n];
            v[0] = u[0];
            for (int k = 1; k < n; k++) {
                long temp = v[k - 1];
                for (int j = k - 2; j >= 0; j--) {
                    temp = (temp * m[j] + v[j]) % m[k];
                }
                v[k] = (u[k] - temp) * gamma[k] % m[k];
                if (v[k] < 0) v[k] += m[k];
            }
            return v;
        }

        private static long invl(long a, long mod) {
            long b = mod;
            long p = 1, q = 0;
            while (b > 0) {
                long c = a / b;
                long d;
                d = a;
                a = b;
                b = d % b;
                d = p;
                p = q;
                q = d - c * q;
            }
            return p < 0 ? p + mod : p;
        }

        private static long[] nttmb(long[] src, int n, boolean inverse, int P, int g) {
            long[] dst = Arrays.copyOf(src, n);

            int h = Integer.numberOfTrailingZeros(n);
            long K = Integer.highestOneBit(P) << 1;
            int H = Long.numberOfTrailingZeros(K) * 2;
            long M = K * K / P;

            int[] wws = new int[1 << h - 1];
            long dw = inverse ? CodeHash.pow(g, P - 1 - (P - 1) / n, P) : CodeHash.pow(g, (P - 1) / n, P);
            long w = (1L << 32) % P;
            for (int k = 0; k < 1 << h - 1; k++) {
                wws[k] = (int) w;
                w = modh(w * dw, M, H, P);
            }
            long J = invl(P, 1L << 32);
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < 1 << i; j++) {
                    for (int k = 0, s = j << h - i, t = s | 1 << h - i - 1; k < 1 << h - i - 1; k++, s++, t++) {
                        long u = (dst[s] - dst[t] + 2 * P) * wws[k];
                        dst[s] += dst[t];
                        if (dst[s] >= 2 * P) dst[s] -= 2 * P;
//					long Q = (u&(1L<<32)-1)*J&(1L<<32)-1;
                        long Q = (u << 32) * J >>> 32;
                        dst[t] = (u >>> 32) - (Q * P >>> 32) + P;
                    }
                }
                if (i < h - 1) {
                    for (int k = 0; k < 1 << h - i - 2; k++) wws[k] = wws[k * 2];
                }
            }
            for (int i = 0; i < n; i++) {
                if (dst[i] >= P) dst[i] -= P;
            }
            for (int i = 0; i < n; i++) {
                int rev = Integer.reverse(i) >>> -h;
                if (i < rev) {
                    long d = dst[i];
                    dst[i] = dst[rev];
                    dst[rev] = d;
                }
            }

            if (inverse) {
                long in = invl(n, P);
                for (int i = 0; i < n; i++) dst[i] = modh(dst[i] * in, M, H, P);
            }

            return dst;
        }

        public static long modh(long a, long M, int h, int mod) {
            long r = a - ((M * (a & ((1L << 31) - 1)) >>> 31) + M * (a >>> 31) >>> h - 31) * mod;
            return r < mod ? r : r - mod;
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        public String scanString() {
            int c = scan();
            if (c == -1) return null;
            while (isWhiteSpace(c)) c = scan();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = scan();
            } while (!isWhiteSpace(c));
            return res.toString();
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

