Match Subarray to Pattern

In the pattern, 1 means the next number is greater than the previous one, 0 means equal, and −1 means less. Count the contiguous subarrays of length pattern length plus 1 whose adjacent relations match the pattern term by term.

This site has made the standard input and output explicit.

输入格式

The first line contains n m, followed by two lines with the array and the pattern. On this site 1≤m<n≤200000, array elements are in −10⁹..10⁹, and pattern values are −1/0/1.

输出格式

Output one integer, the answer.

样例 1

输入：

8 3
4 1 3 4 4 5 5 1
1 0 -1

输出：

1

样例 2

输入：

4 2
1 2 3 4
1 1

输出：

2

样例 3

输入：

3 1
2 2 2
0

输出：

2

样例说明

Example 1: only 4, 5, 5, 1 goes up, flat, then down, so the answer is 1. Example 2: the two overlapping windows 1, 2, 3 and 2, 3, 4 match, so the answer is 2. Example 3: both adjacent windows are all equal, so the answer is 2.