5487: MUH和立方体墙
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：3
通过：1
题目描述
D. MUH和立方体墙
每次测试的时间限制
2 秒
每个测试的内存限制
256 兆字节
输入
标准输入
输出
标准输出
来自圣彼得堡动物园的北极熊Menshykov和Uslada以及来自基辅动物园的大象Horace在某个地方得到了许多木制立方体。他们开始通过将立方体一个放在另一个之上来制作立方体塔。他们将多座塔楼排成一排定义为一堵墙。一堵墙可以由不同高度的塔组成。
贺拉斯是第一个完成墙面的人。他称他的墙为大象。城墙由w塔组成。熊也完成了他们的墙，但他们没有给它一个名字。他们的墙壁由n座塔组成。贺拉斯看着熊塔，想知道：在墙的多少部分，他能“看到一头大象”？他可以在一段连续的塔楼上“看到一头大象”，如果该段塔的高度与贺拉斯墙上塔的高度相匹配。为了看到尽可能多的大象，贺拉斯可以抬高和降低他的墙。他甚至可以将墙壁降低到地面以下（请参阅样品的图片以进行澄清）。
你的任务是计算贺拉斯可以“看到大象”的片段数。
贺拉斯是第一个完成墙面的人。他称他的墙为大象。城墙由w塔组成。熊也完成了他们的墙，但他们没有给它一个名字。他们的墙壁由n座塔组成。贺拉斯看着熊塔，想知道：在墙的多少部分，他能“看到一头大象”？他可以在一段连续的塔楼上“看到一头大象”，如果该段塔的高度与贺拉斯墙上塔的高度相匹配。为了看到尽可能多的大象，贺拉斯可以抬高和降低他的墙。他甚至可以将墙壁降低到地面以下（请参阅样品的图片以进行澄清）。
你的任务是计算贺拉斯可以“看到大象”的片段数。
输入
第一行包含两个整数 n 和 w （1≤n，w≤2·105） - 熊和大象墙上的塔楼数量。第二行包含 n 个整数 a i （1≤a i≤109） − 熊墙上塔的高度。第三行包含 w 整数 b i （1≤b i≤10 9） − 大象墙上塔的高度。
输出
打印熊墙上霍勒斯可以“看到大象”的段数。
例子
输入
13 5 2 4 5 5 4 3 2 2 2 3 3 2 1 3 4 4 3 2
输出
2
注意
左图为样本中的贺拉斯墙，右图为熊墙。贺拉斯可以“看到大象”的片段是灰色的。
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev got hold of lots of wooden cubes somewhere. They started making cube towers by placing the cubes one on top of the other. They defined multiple towers standing in a line as a wall. A wall can consist of towers of different heights.
Horace was the first to finish making his wall. He called his wall an elephant. The wall consists of w towers. The bears also finished making their wall but they didn't give it a name. Their wall consists of n towers. Horace looked at the bears' tower and wondered: in how many parts of the wall can he "see an elephant"? He can "see an elephant" on a segment of w contiguous towers if the heights of the towers on the segment match as a sequence the heights of the towers in Horace's wall. In order to see as many elephants as possible, Horace can raise and lower his wall. He even can lower the wall below the ground level (see the pictures to the samples for clarification).
Your task is to count the number of segments where Horace can "see an elephant".
Horace was the first to finish making his wall. He called his wall an elephant. The wall consists of w towers. The bears also finished making their wall but they didn't give it a name. Their wall consists of n towers. Horace looked at the bears' tower and wondered: in how many parts of the wall can he "see an elephant"? He can "see an elephant" on a segment of w contiguous towers if the heights of the towers on the segment match as a sequence the heights of the towers in Horace's wall. In order to see as many elephants as possible, Horace can raise and lower his wall. He even can lower the wall below the ground level (see the pictures to the samples for clarification).
Your task is to count the number of segments where Horace can "see an elephant".
Input
The first line contains two integers n and w (1≤n,w≤2·105) − the number of towers in the bears' and the elephant's walls correspondingly. The second line contains n integers ai (1≤ai≤109) − the heights of the towers in the bears' wall. The third line contains w integers bi (1≤bi≤109) − the heights of the towers in the elephant's wall.
Output
Print the number of segments in the bears' wall where Horace can "see an elephant".
Examples
Input
13 5 2 4 5 5 4 3 2 2 2 3 3 2 1 3 4 4 3 2
Output
2
Note
The picture to the left shows Horace's wall from the sample, the picture to the right shows the bears' wall. The segments where Horace can "see an elephant" are in gray. 
输入样例 复制
输出样例 复制