C. Простые простые
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это последний класс Профессора R в его карьере преподавателя. Каждый раз, когда Профессор R вел класс, он давал своим ученикам особенную задачу. Как его любимый ученик, вложите всю душу в решение этой задачи в последний раз.

Вам даны два многочлена $$$f(x) = a_0 + a_1x + \dots + a_{n-1}x^{n-1}$$$ и $$$g(x) = b_0 + b_1x + \dots + b_{m-1}x^{m-1}$$$, с целыми положительными коэффициентами. Гарантируется, что общий НОД всех коэффициентов равен $$$1$$$ для обоих многочленов. Другими словами, $$$gcd(a_0, a_1, \dots, a_{n-1}) = gcd(b_0, b_1, \dots, b_{m-1}) = 1$$$. Пусть $$$h(x) = f(x)\cdot g(x)$$$. Пусть $$$h(x) = c_0 + c_1x + \dots + c_{n+m-2}x^{n+m-2}$$$.

Вам также дано простое число $$$p$$$. Профессор R просит вас найти любое такое $$$t$$$, что $$$c_t$$$ не делится на $$$p$$$. Он гарантирует вам, что при данных ограничениях такое $$$t$$$ всегда существует. Если существует несколько таких $$$t$$$, выведите любое из них.

Так как ввод может быть достаточно большим, рекомендуем использовать быстрые способы ввода.

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

Первая строка содержит три целых числа, $$$n$$$, $$$m$$$ и $$$p$$$ ($$$1 \leq n, m \leq 10^6, 2 \leq p \leq 10^9$$$),  — $$$n$$$ и $$$m$$$ это количества членов в $$$f(x)$$$ и $$$g(x)$$$ соответственно (на один большие чем степени соответствующих многочленов), а $$$p$$$  — данное простое число.

Гарантируется, что $$$p$$$ простое.

Вторая строка содержит $$$n$$$ целых чисел $$$a_0, a_1, \dots, a_{n-1}$$$ ($$$1 \leq a_{i} \leq 10^{9}$$$) — $$$a_i$$$ равен коэффициенту при $$$x^{i}$$$ в $$$f(x)$$$.

Третья строка содержит $$$m$$$ целых чисел $$$b_0, b_1, \dots, b_{m-1}$$$ ($$$1 \leq b_{i} \leq 10^{9}$$$)  — $$$b_i$$$ равен коэффициенту при $$$x^{i}$$$ в $$$g(x)$$$.

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

Выведите одно число $$$t$$$ ($$$0\le t \le n+m-2$$$)  — подходящая степень $$$x$$$ в $$$h(x)$$$, коэффициент при которой не делится на данное простое $$$p$$$. Если несколько степеней $$$x$$$ удовлетворяют условию, выведите любую.

Примеры
Входные данные
3 2 2
1 1 2
2 1
Выходные данные
1
Входные данные
2 2 999999937
2 1
3 1
Выходные данные
2
Примечание

В первом примере, $$$f(x)$$$ равен $$$2x^2 + x + 1$$$ и $$$g(x)$$$ равен $$$x + 2$$$, их произведение $$$h(x)$$$ равно $$$2x^3 + 5x^2 + 3x + 2$$$, поэтому ответ может быть 1 или 2, так как и 3 и 5 не делятся на 2.

Во втором примере, $$$f(x)$$$ равен $$$x + 2$$$ и $$$g(x)$$$ равен $$$x + 3$$$, их произведение $$$h(x)$$$ равно $$$x^2 + 5x + 6$$$, поэтому ответом может быть любая из этих степеней, так как ни один коэффициент не делится на данное простое число.