In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#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.
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:
Explanation of the example: The two nice fragments of this chain are 2, 1, 3, 1 and 1, 3, 1, 2.
Sample grading tests:
Task author: Tomasz Walen.<Submit a solution> [0/100]