G

G. Поиск со сдвигом

Гоша измерял температуру воздуха n дней подряд. В результате у него получился некоторый временной ряд. Теперь он хочет посмотреть, как часто встречается некоторый шаблон в получившейся последовательности. Однако температура — вещь относительная, поэтому Гоша решил, что при поиске шаблона длины m (a₁, a₂, ..., a_m) стоит также рассматривать сдвинутые на константу вхождения. Это значит, что если для некоторого числа c в исходной последовательности нашёлся участок вида (a₁ + c, a₂ + c, ... , a_m + c), то он тоже считается вхождением шаблона (a₁, a₂, ..., a_m).

По заданной последовательности измерений X и шаблону A=(a₁, a₂, ..., a_m) определите все вхождения A в X, допускающие сдвиг на константу.

Подсказка: если вы пишете на питоне и сталкиваетесь с TL, то попробуйте заменить какие-то из циклов операциями со срезами.

Формат ввода

В первой строке дано количество сделанных измерений n — натуральное число, не превышающее 10⁴. Во второй строке через пробел записаны n целых чисел x_i, 0 ≤ x_i ≤ 10³ –— результаты измерений. В третьей строке дано натуральное число m –— длина искомого шаблона, 1≤ m ≤ n. В четвёртой строке даны m целых чисел ai — элементы шаблона, 0 ≤ a_i ≤ 10³.

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

Выведите через пробел в порядке возрастания все позиции, на которых начинаются вхождения шаблона A в последовательность X. Нумерация позиций начинается с единицы.

Пример 1

9 3 9 1 2 5 10 9 1 7 2 4 10

1 8

Пример 2

5 1 2 3 4 5 3 10 11 12

1 2 3