宫崎骏的影迷们期待着他的新电影

宫崎骏正在筹备另一部传世经典，他决定将影迷的心愿直接融入到他的下一部杰作中。他的电影由 $N$ 个场景组成，每个场景都旨在传达某种特定的情感。众所周知，大写字母 $A - Z$ 代表了 26 种可能的人类情感（例如用 $H$ 代表快乐，用 $D$ 代表厌恶）。为了让自己的声音被听到， $M$ 位影迷整理了一份他们希望在电影中看到的内容的偏好列表。每位影迷都表示，如果他们在电影中连续看到某段由 $L$ 个情感组成的序列（由长度为 $L$ 的大写字母字符串表示），他们就会感到满足。

由于影迷很容易满足，如果电影中的情感序列与他们期望的足够接近，他们也会感到满足。具体来说，如果电影中的某段情感序列与他们期望的序列相比，仅有 1 个或 2 个情感不同（即匹配了除 1 个或 2 个以外的所有情感），他们也会感到满足。

宫崎骏在创作电影时遇到了一些瓶颈，因此他决定依靠一种屡试不爽的方法来解决任何问题：随机生成。他从均匀分布中随机生成了一个由 $N$ 个场景组成的序列（其中每个场景传达任何一种情感的概率均等）。然后，他将电影中的情感序列交给你，并请你计算有多少位影迷会对这部电影感到满足。

输入格式

输入的第一行是三个空格分隔的整数 $N$ ($1 \le N \le 20\,000$)、 $M$ ($1 \le M \le 100\,000$) 和 $L$ ($1 \le L \le \min(100, N)$)，分别代表电影的长度、影迷的数量以及每位影迷期望的情感序列长度。

输入的下一行包含随机生成的字符串 $S$，代表电影传达的 $N$ 个情感的序列。 $S$ 中的每个字符都是 $A - Z$ 之间的大写字母。保证该字符串是通过从均匀分布中独立选择每个字符而生成的（每个位置选择每个字符的概率均为 $\frac{1}{26}$）。

接下来的 $M$ 行，每行包含一个字符串 $f_i$，代表一位影迷期望的情感序列（不一定两两不同）。 $f_i$ 中的每个字符都是 $A - Z$ 之间的大写字母。与 $S$ 不同，影迷期望的情感序列不会从均匀分布中随机生成。这些影迷的情感序列可以是任意长度为 $L$ 的字符串，且不一定与电影中出现的情感独立生成。

你的提交将在恰好 50 个测试用例上运行。样例仅用于说明。你的每次提交都将在一组新的随机测试用例上运行。

输出格式

输出一行，包含一个整数，代表对这部随机生成的电影感到满足的影迷数量。

样例

输入样例 1

5 3 4
ABCDE
BCDE
BDDC
AEEE

输出样例 1

2