Problem Description

Given two sequences of non-negative integers, $A = (A_1, \dots, A_N)$ and $B = (B_1, \dots, B_M)$, where $ N $ and $ M $ are their respective lengths.

Find the number of integers $ i $ that satisfy $1 \le i \le N - M + 1$ and the following condition:

Condition

Define a contiguous subsequence $ C $ of length $ M $ from $ A $ as $C = (A_i, \dots, A_{i + M - 1})$. Then, update all elements in sequences $ B $ and $ C $ that have a value of $ 0 $ to any positive real number (the updated values can be different for each element). After that, choose an arbitrary positive real number $ t $ and multiply all elements in sequence $ C $ by $ t $. It is possible to make sequences $ B $ and $ C $ identical through these operations.

Input Format

The input is given from the standard input in the following format:

$N\ M$ $A_1\ A_2\ \dots\ A_N$ $B_1\ B_2\ \dots\ B_M$

Output Format

Output the resulting integer.

Sample Input and Output

Sample Input #1

9 4
9 3 0 0 2 99 4 0 0
6 2 0 4

Sample Output #1

4

Sample Input #2

8 2
0 0 0 0 0 0 0 0
0 0

Sample Output #2

7

Notes/Hints

Constraints

• $1 \leq M \leq N \leq 5 \times 10^5$
• $0 \leq A_i \leq 5 \times 10^5$ $(i = 1, \ldots, N)$
• $0 \leq B_i \leq 5 \times 10^5$ $(i = 1, \ldots, M)$

Sample Explanation 1

When $ i = 1 $, update $ B $ to $ (6, 2, 5, 4) $ and $ C = (9, 3, 0, 0) $ to $ (9, 3, 7.5, 6) $, then choose $ t = 2/3 $ to make $ B $ and $ C $ identical. Similarly, for $ i = 2, 3, 4 $, it is possible to match $ B $ and $ C $ through appropriate operations, but not for $ i = 5, 6 $. Therefore, there are $ 4 $ values of $ i $ that satisfy the condition, so the answer is $ 4 $.

见题面 Input 部分

见题面 Output 部分