Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Subsegment Search

By robin_aust · Limits 1s, 512 MB

Galib is the best algorithmist in Bangladesh right now! He challenged Faysal who is also an algorithmist to solve this problem but he got stuck. Can you help him?

You are given two arrays A and  B. Array A contains n integers and array B contains m integers. You have to find out how many times array B appears in array A as a subsegment. You can add x ( -10⁹ ≤ x ≤ 10⁹ )  with all the elements of array B. See the sample explanation below for a better understanding.

Input

The first line contains two integers n (1 ≤ n ≤ 10⁶ ) and m (1 ≤ m  ≤ 10⁶ ) — the length of the arrays. The second line contains n integers Ai (1 ≤ Ai  ≤ 10⁹ ). The third line contains m integers Bi (1 ≤ Bi  ≤ 10⁹ ).

Output

Print the number of times array B appears in array A as a subsegment on a single line.

Samples

InputOutput
6 3
2 2 2 2 2 2
1 1 1

4

InputOutput
4 2
1 1 3 3
5 5

2

InputOutput
10 4
7 1 8 2 6 3 7 1 5 2
8 2 6 3

2


In the first sample, if we add 1 with all the elements of array B, then Array B appears 4 times as a subsegment in the Array A (segments: 1-3, 2-4, 3-5, 4-6).

In the second sample, If we add -4 with all the elements of array B, we get one subsegment in array A (segment: 1-2). And if we add -2, we get another subsegment in array A (segment: 2-4).

Statistics

83% Solution Ratio

pathanEarliest, 4M ago

MoRanSky.835291Fastest, 0.0s

fragilisticLightest, 8.1 MB

fragilisticShortest, 531B