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

Условие

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

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

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

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

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

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

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

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

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

5 2
1 1 2 1 1
1 1

2

7 2
8 5 9 7 6 7 1
9 5

0