Background

Tired of fighting the original bosses, FyFive decided to make a Hollow Knight Mod Boss called “Successful Champion”.

Problem Description

Similar to the original Failed Champion, the Successful Champion also has a big armor that cannot be “healed by soul”. However, what makes the Successful Champion harder is that its armor can only be damaged with a specific striking pattern. A strike sequence that can deal damage is called an “effective strike”.

As the designer of this Mod Boss, FyFive set a “standard sequence” that can produce effective strikes. To reduce the difficulty of execution, an effective strike can be produced as long as the strike order is “similar” to the standard sequence. Here, “similar” means: for a strike sequence, if you scale the lengths of all consecutive blocks of identical strikes by the same factor, and can obtain another sequence, then the two sequences are said to be “similar”.

For example:

• 112244 and 111222444 are similar.
• 111333 and 13 are also similar.
• 226 and 226 are also similar.
• 33889 and 33388899 are not similar.

Since the Boss is still in the stage of tuning the standard sequence, FyFive set the Boss’s HP to infinity. But then he cannot compute how many effective strikes his strike sequence produces under the current standard sequence by comparing the initial HP and the final HP. So please help FyFive.

Note: If it is possible to produce multiple effective strikes at the same time, then multiple effective strikes are indeed produced. For example, when the strike sequence is 11 and the standard sequence is 1, this strike sequence produces $3$ effective strikes, because the first 1 and the second 1 are both similar to the standard sequence, and 11 is also similar to the standard sequence. If the standard sequence is 11, there are also $3$ effective strikes. If the standard sequence is 12, then no effective strike is produced. Similarly, when the strike sequence is 6666 and the standard sequence is 66, then a total of $10$ effective strikes are produced.

Formally,

Definition: Let sequence $\Alpha$ be

$$\underbrace{AA...A}_{a_1个}\underbrace{BB...B}_{a_2个}\underbrace{CC...C}_{a_3个}...$$

and sequence $\Beta$ be

$$\underbrace{AA...A}_{b_1个}\underbrace{BB...B}_{b_2个}\underbrace{CC...C}_{b_3个}...$$

where $A,B,C,a_1,a_2,a_3,...,b_1,b_2,b_3,...\in 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 called similar sequences to each other.

In particular, a sequence of length $0$ is not similar to any sequence.

It is not hard to prove that under this definition, similarity between sequences is transitive.

Given sequence $A$, compute how many substrings are similar to the 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

Output one positive integer in a single line, representing the total number of effective strikes.

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

7

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

2

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

1

Hint

Constraints:

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

For $100\%$ of the testdata, 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 exists exactly one $k\in[1,m-1]$ such that $\forall \ i,j\in[1,k]$，$B_i=B_j$; and $\forall \ i,j\in[k+1,m]$，$B_i=B_j$。

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

Translated by ChatGPT 5