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
| Input | Output |
|---|---|
6 3 2 2 2 2 2 2 1 1 1 | 4 |
| Input | Output |
|---|---|
4 2 1 1 3 3 5 5 | 2 |
| Input | Output |
|---|---|
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).
