← 返回题目列表

Codeforces · 360/D

D. Levko 和套装

中文机器翻译题面 查看原题

Levko非常喜欢各种套装。

Levko 有两个整数数组 a1, a2, ... , an 和 b1, b2, ... , bm 和一个素数 p。今天他生成了 n 组。我们来描述一下第i个集合的生成过程:

1. 首先它有一个数字 1。
2. 让我们从该集合中取出任意元素 c。对于所有 j (1 ≤ j ≤ m),如果数字 (c·aibj) mod p 没有出现在集合中,则将其添加到集合中。
3. 重复步骤 2,只要我们可以向集合中添加至少一个元素即可。

Levko 想知道,有多少个数字属于至少一组。也就是说,他想知道n个生成集的并集有多大。

输入

第一行包含三个整数 n、m 和 p (1 ≤ n ≤ 104, 1 ≤ m ≤ 105, 2 ≤ p ≤ 109),p 是质数。

第二行包含空格分隔的整数 a1, a2, ... , an (1 ≤ ai < p)。第三行包含空格分隔的整数 b1, b2, ... , bm (1 ≤ bi ≤ 109)。

输出

单个数字 — 集合并集的大小。

示例

输入 #1

1 1 7
2
5

输出 #1

3

输入 #2

1 2 7
2
2 4

输出 #2

3

输入 #3

2 1 7
1 6
2

输出 #3

1

输入#4

2 1 7
1 6
5

输出#4

2