这是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}$$$。对于两个给定的多项式,保证系数的累积 GCD 等于 $$$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)$$$ 分别(比相应多项式的次数多 1),$$$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$$$ 有多个幂满足条件,则打印任意一个。
示例
输入 #1
3 2 2 1 1 2 2 1
输出 #1
1
输入 #2
2 2 999999937 2 1 3 1
输出 #2
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$$$,因此答案可以是任何幂,因为没有系数可以被给定素数整除。