Description

Little Bytie loves to play with colorful chains. Each chain consists of a certain number of colorful links. Bytie finds a contiguous fragment of a chain nice if it contains exactly $l_i$ links of color $c_i$ for every $i$ in $[1, m]$, and moreover contains no links of any other colors. The appeal of a chain is the number of its contiguous fragments that are nice.

Given a sequence of length $n$ representing the colors of the chain and $m$ conditions (each condition gives a color $c_i$ and a required count $l_i$), count how many contiguous substrings are nice, that is:

• For every $c_i$ among the $m$ conditions, the substring contains exactly $l_i$ occurrences of $c_i$.
• For any color not listed among the $m$ conditions, the substring contains none of it.

Input Format

• The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 10^6$). These are the length of the chain and the number of conditions.
• The second line contains $m$ integers $l_1, l_2, \dots, l_m$ ($1 \le l_i \le n$).
• The third line contains $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n$). These define that a nice fragment must contain exactly $l_i$ links of color $c_i$ for each $i$ and no links of any other colors.
• The fourth line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), the colors of successive links of the chain.

Output Format

Print a single integer, the number of nice contiguous fragments in the chain.

7 3
2 1 1
1 2 3
4 2 1 3 1 2 5

2

Hint

Constraints:

For $100\%$ of the testdata, $1 \le m \le n \le 10^6$ and $1 \le a_i, l_i, c_i \le n$.

Translated by ChatGPT 5