Это последний класс Профессора 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\), выведите любое из них.
Так как ввод может быть достаточно большим, рекомендуем использовать быстрые способы ввода.
Выходные данные
Выведите одно число \(t\) (\(0\le t \le n+m-2\)) — подходящая степень \(x\) в \(h(x)\), коэффициент при которой не делится на данное простое \(p\). Если несколько степеней \(x\) удовлетворяют условию, выведите любую.
Примечание
В первом примере, \(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\), поэтому ответом может быть любая из этих степеней, так как ни один коэффициент не делится на данное простое число.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 2
1 1 2
2 1
|
1
|
|
2
|
2 2 999999937
2 1
3 1
|
2
|