Задача E. Диагностика

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

В ходе исследований конструкторское бюро Завода выявило ряд последовательностей в диагностических сигналах новейшей разработки, которые говорят о дефектах и неполадках. Ведущему программисту КБ Петру поручили разработать программу, определяющую выявленные последовательности в полученных сигналах.

Последовательность сигналов подается в виде массива целых чисел A и размерностью N > 1. Искомая последовательность определяется массивом целых чисел T с размерностью M < N.

Требуется написать программу, которая выведет целое число – количество последовательностей T, встреченных в массиве A.

Формат входных данных

В первой строке вводятся два целых числа через пробел N и M, 1 < N ≤ 105, 1 ≤ M ≤ N – количество элементов массива сигналов A и длина последовательности T соответственно.

Следующие две строки содержат по N и M целых чисел соответственно – значения измеренных сигналов и искомой последовательности.

Формат выходных данных

В единственной строке выведите целое число – сколько раз повторяется последовательность T в последовательности A.

Примеры тестов

Стандартный вход Стандартный выход
1
5 2
1 1 2 1 1
1 1
2
2
7 2
8 5 9 7 6 7 1
9 5
0

0.209s 0.027s 13