505026 - 集合的并集

【题目描述】集合的并集(union)

有两个整数数组{a1,a2,...,an}和{b1,b2,...,bm},以及一个素数p。 我们利用这些ai来生成n个集合,具体的生成方式如下: (1)首先有一个数字1; (2)从集合中任取一个元素c,遍历b数组,并计算 。如果计算结果不在当前集合中,就将新的计算结果放入集合。 (3)重复步骤(2),直到集合中不再出现新的元素为止。 请输出最终所有n个集合的并集有多少个元素。

输入

第一行有三个整数n,m,p(1≤n≤10^4,1≤m≤10^5,2≤p≤10^9),其中p是质数。 第二行包含n个整数ai(1≤ai≤p)。 第三行包含m个整数bi(1≤bi≤10^9)。

输出

输出一个数字,表示对应集合并集的大小。

样例

输入

1 2 7
2
2 4

输出

3
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题