Rabbit Jumping on a Circular Track

Consider a circular track consisting of n cells numbered from 0 to n-1. A rabbit moves along the track with a fixed step length k. If a rabbit is at cell i, after one second it will jump to cell \( (i + k) \bmod n \).

There are m rabbits on the track. The i-th rabbit starts at cell \( p_i \). Over time, rabbits visit some cells, while some cells might never be reached by any rabbit.

Your task is to determine the number of cells that will never be visited by any rabbit.

Hint: For a given rabbit starting at cell \( p \), it will only visit cells that are congruent to \( p \) modulo \( d \), where \( d = \gcd(n, k) \). Use this observation to count the unreachable cells.

inputFormat

The input consists of two lines:

1. The first line contains three integers n, m, and k separated by spaces.
2. The second line contains m integers \( p_0, p_1, ..., p_{m-1} \) representing the starting cells of the rabbits.

\(1 \leq n \leq 10^9\), \(1 \leq m \leq 10^5\), and \(0 \leq p_i < n\).

outputFormat

Output a single integer representing the number of cells that will never be visited by any rabbit.

sample

10 2 4
1 5

5