Problem Background

Having grown tired of the original Boss, FyFive decided to create a Mod Boss for Hollow Knight, named "Successful Champion."

Problem Description

Similar to the original Failed Champion, the Successful Champion also has a large armor that cannot be revived. However, the challenge with the Successful Champion lies in the fact that its armor can only be damaged by specific strike patterns, known as "effective strikes."

As the designer of the Mod Boss, FyFive has set a "standard sequence" that can cause effective strikes. To reduce the difficulty of operation, a strike sequence can cause effective strikes if it is "similar" to the standard sequence. The definition of "similarity" here is that for a strike sequence, if all consecutive segments of the same strike are scaled simultaneously to obtain another sequence, then these two sequences are considered "similar."

For example:
- 112244 and 111222444 are similar,
- 111333 and 13 are similar,
- 226 and 226 are similar,
- 33889 and 33388899 are not similar.

Since the Boss is still in the stage of adjusting the standard sequence, FyFive has set the Boss's health to infinity. However, he cannot calculate how many effective strikes his sequence can cause under the current standard sequence by comparing the initial and final health. Therefore, he asks you, a capable individual, for help!

Note: For situations where multiple effective strikes might occur simultaneously, they will indeed cause multiple effective strikes. For example, if the strike sequence is 11 and the standard sequence is 1, this strike sequence will cause 3 effective strikes because both the first and second 1 are similar to the standard sequence, and 11 is also similar to the standard sequence. If the standard sequence is 11, there will also be 3 effective strikes. If the standard sequence is 12, no effective strikes will occur. Similarly, when the strike sequence is 6666 and the standard sequence is 66, a total of 10 effective strikes will occur.

Formally,

Definition: If sequence $\Alpha$ is
$$\underbrace{AA...A}_{a_1\text{ times}}\underbrace{BB...B}_{a_2\text{ times}}\underbrace{CC...C}_{a_3\text{ times}}...$$
and sequence $\Beta$ is
$$\underbrace{AA...A}_{b_1\text{ times}}\underbrace{BB...B}_{b_2\text{ times}}\underbrace{CC...C}_{b_3\text{ times}}...$$
where $A, B, C, a_1, a_2, a_3, ..., b_1, b_2, b_3, ... \in \mathbb{N}_+$.

If $\frac{a_1}{b_1} = \frac{a_2}{b_2} = \frac{a_3}{b_3} = ... = k, k > 0$, then $\Alpha$ and $\Beta$ are considered similar sequences.

Specifically, a sequence of length 0 is not similar to any sequence.

It is easy to prove that similarity between sequences is transitive under this definition.

Determine how many substrings of a given sequence $A$ are similar to a given sequence $B$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, representing the strike sequence $A$, separated by spaces.

The third line contains $m$ integers, representing the standard sequence $B$, separated by spaces.

Output Format

A single line containing a positive integer, representing the total number of effective strikes caused.

Sample Input and Output

Sample Input #1

7 3
6 7 6 6 6 5 4
6 6 6

Sample Output #1

7

Sample Input #2

8 6
4 4 2 2 4 4 2 2
4 4 4 4 2 2

Sample Output #2

2

Sample Input #3

8 7
3 3 3 2 2 2 1 1
3 3 3 2 2 2 1

Sample Output #3

1

Notes/Hints

Data Range:

For $100\%$ of the data, it is guaranteed that $\forall\ i \in [1, n], 1 \leq A_i \leq 7$; $\forall\ i \in [1, m], 1 \leq B_i \leq 7$.

For $100\%$ of the data, it is guaranteed that $1 \leq n, m \leq 5 \times 10^6$.

Special Property A: It is guaranteed that $\forall\ i, j \in [1, m], B_i = B_j$.

Special Property B: It is guaranteed that there is exactly one $k \in [1, m-1]$ such that $\forall\ i, j \in [1, k], B_i = B_j$; $\forall\ i, j \in [k+1, m], B_i = B_j$.

Special Property C: It is guaranteed that in the 10th data point, $n, m \leq 5 \times 10^5$, and in other points, there are no more than 100 different lengths of consecutive segments.

见题面 Input 部分

见题面 Output 部分