题面

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)=a0+a1x+⋯+an−1xn−1">f(x)=a0+a1x+?+an?1xn?1 and g(x)=b0+b1x+⋯+bm−1xm−1">g(x)=b0+b1x+?+bm?1xm?1, with positive integral coefficients. It is guaranteed that the cumulative GCD of the coefficients is equal to 1">11 for both the given polynomials. In other words, gcd(a0,a1,…,an−1)=gcd(b0,b1,…,bm−1)=1">gcd(a0,a1,…,an?1)=gcd(b0,b1,…,bm?1)=1. Let h(x)=f(x)⋅g(x)">h(x)=f(x)?g(x). Suppose that h(x)=c0+c1x+⋯+cn+m−2xn+m−2">h(x)=c0+c1x+?+cn+m?2xn+m?2.

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

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

Input

The first line of the input contains three integers, n">nn, m">mm and p">pp (1≤n,m≤106,2≤p≤109">1≤n,m≤1e6,2≤p≤1e9),  — n">nn and m">mm are the number of terms in f(x)">f(x)f(x) and g(x)">g(x)g(x) respectively (one more than the degrees of the respective polynomials) and p">pp is the given prime number.

It is guaranteed that p">p is prime.

The second line contains n">nn integers a0,a1,…,an−1">a0,a1,…,an?1 (1≤ai≤109">1≤ai≤1e9) — ai">ai is the coefficient of xi">xi in f(x)">f(x).

The third line contains m">mm integers b0,b1,…,bm−1">b0,b1,…,bm?1 (1≤bi≤109">1≤bi≤1e9)  — bi">bi is the coefficient of xi">xi in g(x)">g(x).

Output

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

Examples

Input

3 2 2
1 1 2
2 1

Output

1

Input

2 2 999999937
2 1
3 1

Output

2

 大意

给出两个非负整系数多项式f(x)，g(x)和一个质数p，求一个数t，使得对于两个多项式的乘积h(x)=f(x)g(x)，其次数为t的项不能被p整除。如果有多种结果，输出任意一个。

 题解

这是我ACM校队预备役选拔赛第二场的一道题，在赛场上我没想出来……后来知道解法之后，我不由得赞叹：还是我的技术力太低了吗……不过我在第三场选拔赛的时候成功入选预备役，被我丢弃多时的博客再次被我捡了回来【滑稽】。

回想多项式乘法，我们假设f(x)的i次项系数为ai，g(x)的j次项系数为bj，h(x)的k次项系数为ck，则有ck=a0bk+a1b(k-1)+a2b(k-2)+...+akb0。我们从低位往高位考虑，因为题目保证给出的数p一定是个质数，所以如果ai无法被p整除，bj无法被p整除，那么aibj也一定无法被p整除。所以，我们把两个多项式的系数都对p取模，从低位往高位扫，扫到两个多项式内第一个模p不为0的数，假设是ai，bj。那么，含有项aibj的系数就一定无法被p整除。哪一个系数含有aibj呢？自然是c(i+j)了。下面上赛后补题的AC代码：

#include 
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rrep(i,a,b) for(register int i=a;i>=b;--i)
#define grp int T;scanf("%d",&T);rep(C,1,T)
#define grpc int T;cin>>T;rep(C,1,T)
#define etr putchar('\n')
#define in1(a) scanf("%d",&a)
#define in2(a,b) scanf("%d %d",&a,&b)
#define in3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define elif else if
#define mem(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int n, m, p;
int a[1000010], b[1000010];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> p;
	rep(i, 0, n - 1) {
		cin >> a[i];
		a[i] %= p;
	}
	rep(i, 0, m - 1) {
		cin >> b[i];
		b[i] %= p;
	}
	int f1, f2;
	for (f1 = 0; f1 < n; ++f1) {
		if (a[f1] != 0) break;
	}
	for (f2 = 0; f2 < m; ++f2) {
		if (b[f2] != 0) break;
	}
	cout << f1 + f2 << endl;

	return 0;
}


/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +
*　　　┃　　　┃ + + + + + +
*　　　┃　 　 ┗━━━┓ 　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/