Bobo 被要求解决以下经典的模式匹配问题：

给定两个字符串 $s$ 和 $t$，计算 $s$ 在 $t$ 中作为子串出现了多少次。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n, m \le 10^7$)，分别表示字符串 $s$ 和 $t$ 的长度。 下一行包含一个长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。 下一行包含一个长度为 $m$ 的字符串 $t$，仅由小写英文字母组成。 请参阅“说明”部分以获取更具体的限制。

输出格式

输出一行一个整数，表示 $s$ 在 $t$ 中作为子串出现的次数。

样例

输入格式 1

3 7
aba
abababc

输出格式 1

2

输入格式 2

1 11
a
abracadabra

输出格式 2

5

输入格式 3

8 10
possible
impossible

输出格式 3

1

输入格式 4

10 21
pleasenote
theunusualmemorylimit

输出格式 4

0

说明

由于技术原因，本题以交互式问题的形式实现。你可以将其视为一个普通的传统问题，唯一的限制是你的程序只允许按顺序读取输入最多一次。例如，明确禁止读取整个输入后，将输入流重置到开头并重新读取。此外，你必须在输出答案之前读取所有输入，否则你可能无法获得正确的判决。