Чтобы загружать задачи на олимпиады в 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$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 14 | $$$n, m \le 1000$$$ | первая ошибка | |
2 | 11 | $$$q = 1$$$ | первая ошибка | |
3 | 20 | $$$a_i = 0$$$ для всех $$$i$$$ | первая ошибка | |
4 | 23 | $$$q = m$$$ | первая ошибка | |
5 | 32 | нет | 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