Ringed Genesis

Enzyme runs through the Ringed Genesis，just like Rabbit runs through a Ring.

有一个长长的环，环由 $n$ 个格子首尾相接形成，依次编号 $0$ 至 $n-1$。 还有一种动物——兔子。兔子的步长为 $k$。若兔子当前在第 $i$ 个格子，那么下一秒它将跳到第 $(i+k)\bmod n$ 个格子。 现在有 $m$ 只兔子，第 $i$ 只兔子的初始格子为第 $p_i$ 个格子。随着时间的流逝，有些格子被兔子经过了，有些却一直没有被兔子经过。 你需要求出的是，有多少个格子永远不可能被兔子经过。

从标准输入中读取数据。 第一行，三个正整数 $n,m,k$，表示环长，兔子数，步长。 第二行，$m$ 个非负整数 $p_1,p_2,\dots,p_m$，表示兔子的初始格子。

输出数据至标准输出中。 共一行，一个整数，表示答案。

4 2 2
0 1

0

4 2 2
0 2

2

子任务 1（$10\%$）：$k=1$。 子任务 2（$20\%$）：$k|n$，也即 $\gcd(k,n)=k$。 子任务 3（$25\%$）：$1\leq n\leq 1000$，$1\leq m\leq 1000$。 子任务 4（$45\%$）：无特殊限制。 对于全部数据，$1 \leq n \leq 10^6$，$1 \leq m \leq 10^6$，$1 \leq k \leq n$。