In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

<Submit a solution> [0/100]**Task statistics**

Number of users: 267

Number of users with 100 points: 137

Average result: 86.9888

# Colorful Chain

### Memory limit: 128 MB

## Input

## Output

## Example

Number of users: 267

Number of users with 100 points: 137

Average result: 86.9888

Little Bytie loves to play with colorful chains. He already has quite an impressive collection, and some of them he likes more than the others. Each chain consists of a certain number of colorful links. Byteasar has noticed that Bytie's sense of aesthetics is very precise. It turns out that Bytie finds a contiguous fragment of a chain nice if it contains exactly links of color links of color links of color , and moreover it contains no links of other colors. A chain's appeal is its number of (contiguous) fragments that are nice. By trial and error, Byteasar has determined the values and . Now he would like to buy a new chain, and therefore asks you to write a program to aid him in shopping.

The first line of the standard input gives two integers, and (), separated by a single space. These are the length of the chain and the length of a nice fragment's description. The second line gives integers, (), separated by single spaces. The third line gives integers, (, for ), also separated by single spaces. The sequences and define a nice fragment of a chain - it has to contain exactly links of color . The fourth line gives integers, (), separated by single spaces, that are the colors of successive links of the chain.

In tests worth 50% of total points the constraint holds in addition.

Your program is to print a single integer, the number of nice contiguous fragments in the chain, to the first and only line of the standard output.

For the input data:

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

the correct result is:

2

**Explanation of the example:** The two nice fragments of this chain are 2, 1, 3, 1 and 1, 3, 1, 2.

**Sample grading tests:**

`1ocen`, , two nice fragments with the second one following the first one immediately, with neither overlap nor additional links in between;`2ocen`, , the length of the nice fragment exceeds the length of the whole chain (the result is 0);`3ocen`, , three overlapping nice fragments;`4ocen`, , the nice fragment contains a single link of the colors , and the chain is a sequence of links of colors 1, 2, ..., 499, 500, 500, 499, ..., 2, 1 (the result is 2);`5ocen`, , the nice fragment contains a single link of color 1 and two links of color 2; the chain consists of links of colors 1, 2, 2, 1, 2, 2, ... (the result is ).

*Task author: Tomasz Walen.*