CF1316C.Primitive Primes

It is Professor R's last class of his teaching career. Every time Professor R taught a class, he gave a special problem for the students to solve. You being his favourite student, put your heart into solving it one last time.

You are given two polynomials $f(x) = a_0 + a_1x + \dots + a_{n-1}x^{n-1}$ and $g(x) = b_0 + b_1x + \dots + b_{m-1}x^{m-1}$, with positive integral coefficients. It is guaranteed that the cumulative GCD of the coefficients is equal to $1$ for both the given polynomials. In other words, $gcd(a_0, a_1, \dots, a_{n-1}) = gcd(b_0, b_1, \dots, b_{m-1}) = 1$. Let $h(x) = f(x)\cdot g(x)$. Suppose that $h(x) = c_0 + c_1x + \dots + c_{n+m-2}x^{n+m-2}$.

You are also given a prime number $p$. Professor R challenges you to find any $t$ such that $c_t$ isn't divisible by $p$. He guarantees you that under these conditions such $t$ always exists. If there are several such $t$, output any of them.

As the input is quite large, please use fast input reading methods.

这是教授 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$，输出其中任意一个即可。

由于输入规模较大，请使用快速输入读取方法。

The first line of the input contains three integers, $n$, $m$ and $p$ ($1 \leq n, m \leq 10^6, 2 \leq p \leq 10^9$), — $n$ and $m$ are the number of terms in $f(x)$ and $g(x)$ respectively (one more than the degrees of the respective polynomials) and $p$ is the given prime number.

It is guaranteed that $p$ is prime.

The second line contains $n$ integers $a_0, a_1, \dots, a_{n-1}$ ($1 \leq a_{i} \leq 10^{9}$) — $a_i$ is the coefficient of $x^{i}$ in $f(x)$.

The third line contains $m$ integers $b_0, b_1, \dots, b_{m-1}$ ($1 \leq b_{i} \leq 10^{9}$) — $b_i$ is the coefficient of $x^{i}$ in $g(x)$.

输入的第一行包含三个整数 $n$、$m$ 和 $p$（$1 \leq n, m \leq 10^6$，$2 \leq p \leq 10^9$），其中 $n$ 和 $m$ 分别为多项式 $f(x)$ 和 $g(x)$ 的项数（即分别比对应多项式的次数大 $1$），$p$ 为给定的质数。

保证 $p$ 是质数。

第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$（$1 \leq a_{i} \leq 10^{9}$），其中 $a_i$ 是 $f(x)$ 中 $x^{i}$ 项的系数。

第三行包含 $m$ 个整数 $b_0, b_1, \dots, b_{m-1}$（$1 \leq b_{i} \leq 10^{9}$），其中 $b_i$ 是 $g(x)$ 中 $x^{i}$ 项的系数。

Print a single integer $t$ ($0\le t \le n+m-2$) — the appropriate power of $x$ in $h(x)$ whose coefficient isn't divisible by the given prime $p$. If there are multiple powers of $x$ that satisfy the condition, print any.

输出一个整数 $t$（$0\le t \le n+m-2$）——即多项式 $h(x)$ 中幂次为 $x^t$ 的项的系数不能被给定质数 $p$ 整除。若存在多个满足条件的幂次，输出任意一个即可。

In the first test case, $f(x)$ is $2x^2 + x + 1$ and $g(x)$ is $x + 2$, their product $h(x)$ being $2x^3 + 5x^2 + 3x + 2$, so the answer can be 1 or 2 as both 3 and 5 aren't divisible by 2.

In the second test case, $f(x)$ is $x + 2$ and $g(x)$ is $x + 3$, their product $h(x)$ being $x^2 + 5x + 6$, so the answer can be any of the powers as no coefficient is divisible by the given prime.

在第一个测试用例中，$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$，因此答案可以是任意幂次，因为给定素数不能整除 $h(x)$ 的任一系数。