Доступ к серверу
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы загружать задачи на олимпиады в PCMS, требуется доступ к серверу, на котором сам PCMS запущен. Обычно с этим проблем не возникает, но в этот раз что-то пошло не так, и код доступа был утерян, поэтому задачи были загружены прямо перед началом контеста.

Код доступа — массив $$$a$$$ длины $$$m$$$ из целых чисел от $$$0$$$ до $$$139$$$. Известно, что длина кода равна $$$m$$$. Он был зашифрован с помощью шифра Виженера ключом $$$k$$$ длины $$$q$$$ ($$$q$$$ — делитель $$$m$$$). Для шифрования код разбивается на блоки длины $$$q$$$, после чего в каждом блоке $$$i$$$-й символ увеличивается на $$$k_i$$$ по модулю $$$139$$$. Иными словами, $$$b_{i \cdot q + j}$$$ при $$$0 \le i < \frac{m}{q}$$$ и $$$1 \le j \le q$$$ заменяется на $$$(b_{i \cdot q + j} + k_j) \bmod 139$$$.

Обозначим зашифрованный код за $$$\mathtt{encode}(a, k)$$$. Чтобы код можно было восстановить, хранится массив $$$b$$$ длины $$$n$$$, в котором некоторый отрезок занят записанными подряд $$$k$$$ и $$$\mathtt{encode}(a, k)$$$. Например, если ключ равен $$$[1, 2, 3]$$$, а код равен $$$[1, 5, 138, 12, 137, 60]$$$, где-то в массиве $$$b$$$ будет присутствовать отрезок $$$$$$[\ldots, \textcolor{blue}{1, 2, 3}, \textcolor{red}{2, 7, 2, 13, 0, 63}, \ldots] \text{.}$$$$$$

Организаторы олимпиады справились восстановить доступ в систему, поэтому вам дается более простая задача. Вам дан массив $$$b$$$, а также уже восстановленный код $$$a$$$ и длина ключа $$$q$$$. Найдите любое вхождение в $$$b$$$ отрезка, удовлетворяющего условию.

Входные данные

В первой строке ввода через пробел даны целые числа $$$n$$$, $$$m$$$ и $$$q$$$ — длины имеющегося массива, кода и ключа, соответственно ($$$1 \le q \le m \le 10^6$$$; $$$q + m \le n \le 10^6$$$). Гарантируется, что $$$m$$$ делится на $$$q$$$.

Во второй строке через пробел перечислены $$$m$$$ целых чисел $$$a_i$$$ — элементы кода доступа $$$a$$$ ($$$0 \le a_i < 139$$$). В третьей строке в том же формате перечислены $$$n$$$ целых чисел $$$b_i$$$ — элементы массива $$$b$$$ ($$$0 \le b_i < 139$$$).

Выходные данные

Выведите единственное целое число от $$$1$$$ до $$$n$$$ — позицию левой границы искомого отрезка массива $$$b$$$. Если существует несколько отрезков, удовлетворяющих условию, выведите левую границу любого из них.

Если данные некорректны, и удовлетворяющего условию отрезка не существует, выведите $$$-1$$$.

Система оценки

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
114$$$n, m \le 1000$$$первая ошибка
211$$$q = 1$$$первая ошибка
320$$$a_i = 0$$$ для всех $$$i$$$первая ошибка
423$$$q = m$$$первая ошибка
532нет1 – 4первая ошибка

Примеры

Входные данные
12 6 3
1 5 138 12 137 60
0 5 1 2 3 2 7 2 13 0 63 44
Выходные данные
3
Входные данные
18 6 3
1 2 1 2 4 2
72 71 72 0 0 0 1 2 1 2 4 2 3 6 3 4 8 4
Выходные данные
4
Входные данные
5 2 2
1 1
1 2 3 4 5
Выходные данные
-1