Subarray Matches a Comparison Pattern

Given an integer array a and a pattern p of length m. The values of p are 1, 0, and −1, requiring the next element to be greater than, equal to, or less than the previous one, respectively. Count the contiguous subarrays of length exactly m+1 whose adjacent comparisons all match the pattern; overlaps are allowed.

输入格式

The first line contains n m (2≤n≤10000, 1≤m<n); the second line contains n integers (−10⁹..10⁹); the third line contains m pattern values.

输出格式

Output the answer as described; separate multiple results with spaces in order, and output an empty line for an empty array.

样例 1

输入：

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

输出：

2

样例 2

输入：

4 2
2 2 2 2
0 0

输出：

2

样例 3

输入：

3 1
3 2 1
1

输出：

0

样例说明

Example 1: [1,4,4,1] starting at 0 and [3,5,5,3] starting at 4 both go up, stay equal, then go down in order; no other window matches, so there are 2 in total.