Migrated from Lutece 3051 Tarp-Sirrom-Tunk

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在 Arozustan 国，存在一种古老而又神秘的算法，名为 Tarp-Sirrom-Tunk。它解决的是如下问题：

• 给定一个主串 $S$ 和一个模式串 $T$，找出 $S$ 中所有与 $T$ 相同的子串（这些子串允许互相部分重叠，但不允许完全重合）。 $\text{}$

这个算法在 Arozustan 国已经失传了。然而，最近他们遭受了敌国的攻击，为了破译敌国的战争指令，他们急需 Tarp-Sirrom-Tunk 算法来攻破难关。

善良的人类，你能帮他们重新发明这个算法吗？你只需要输出 $S$ 中与 $T$ 相同的子串的总数就好了。

由于 Arozustan 人的语言里有 $\text{TREE}(3)$ 种字符，所以他们只好把每个字符都转换成对应的十进制数再交给你，让你帮他们计算出答案。

Input

第一行两个整数 $n$ 和 $m$ $(1\le m\le n\le 10^6)$，表示 $S$ 和 $T$ 的长度；

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$ $(1\le a_i\le n)$，表示 $S$ 中的字符转换为数字后的序列；

第三行 $m$ 个整数 $b_1,b_2,\ldots,b_m$ $(1\le b_i\le n)$，表示 $T$ 中的字符转换为数字后的序列。

Output

输出一行一个整数，表示答案。

Samples

5 3
1 2 1 2 1
1 2 1

2

Note

样例解释：

$S$ 中可以找到两个与 $T$ 相同的子串，分别是从第 $1$ 个到第 $3$ 个字符的子串和从 $3$ 个到第 $5$ 个字符的子串。

本题请尽量使用具有完全正确性的算法（即不存在概率性输出错误答案的情况）。否则题解会酌情扣分。

Resources

2023 UESTC ICPC Training for String