CF1740I.Arranging Crystal Balls

In the world of Compfestnesia, Pak Chanek discovers a secret underground dungeon. Inside it, there is a treasure chest that is surrounded by $n$ statues that are arranged in a circular manner. The statues are numbered from $0$ to $n-1$ with statue $i$ being to the left of statue $i+1$ and statue $n-1$ being to the left of statue $0$.

Pak Chanek observes that each statue is holding a crystal ball with an integer between $0$ and $m-1$ inclusive. Let's say the integer in the crystal ball of statue $i$ is $a_i$.

The dungeon provides instructions that every integer in the crystal balls must be $0$ in order to open the treasure chest. To achieve that, Pak Chanek is given an integer $k$, and he can do zero or more operations. In a single operation, Pak Chanek does the following:

1. Choose exactly $k$ consecutive statues. In other words, choose the statues $p, (p+1) \bmod n, (p+2) \bmod n, (p+3) \bmod n, \ldots, (p+k-1) \bmod n$ for some chosen index $p$.
2. Do one of the following:
   • For all chosen statues, change their values of $a_i$ into $(a_i+1) \bmod m$.
   • For all chosen statues, change their values of $a_i$ into $(a_i-1) \bmod m$.

Help Pak Chanek find the minimum possible number of operations to open the treasure chest.

在 Compfestnesia 世界中，Pak Chanek 发现了一座秘密的地下迷宫。迷宫内部有一只宝箱，被 $n$ 座呈环形排列的雕像所环绕。这些雕像编号为 $0$ 到 $n-1$，其中雕像 $i$ 位于雕像 $i+1$ 的左侧，而雕像 $n-1$ 位于雕像 $0$ 的左侧。

Pak Chanek 观察到，每座雕像都手持一个水晶球，水晶球中包含一个介于 $0$ 到 $m-1$（含端点）之间的整数。设雕像 $i$ 手持水晶球中的整数为 $a_i$。

迷宫提供了指示：只有当所有水晶球中的整数均为 $0$ 时，宝箱才能开启。为达成这一目标，Pak Chanek 获得了一个整数 $k$，并可执行零次或多次操作。每次操作中，Pak Chanek 执行以下步骤：

1. 恰好选择 $k$ 座连续的雕像。换言之，对某个选定的下标 $p$，选择雕像 $p,\ (p+1) \bmod n,\ (p+2) \bmod n,\ (p+3) \bmod n,\ \ldots,\ (p+k-1) \bmod n$。
2. 执行以下两种操作之一：
   • 对所有被选中的雕像，将其 $a_i$ 的值更新为 $(a_i+1) \bmod m$；
   • 对所有被选中的雕像，将其 $a_i$ 的值更新为 $(a_i-1) \bmod m$。

请帮助 Pak Chanek 找出开启宝箱所需的最少操作次数。

The first line contains three integers $n$, $m$, and $k$ ($2 \leq n,m \leq 10^6$, $nm \leq 2 \cdot 10^6$, $1 \leq k \lt n$) — the number of statues, the bound of the integers in the crystal balls, and the number of statues that can be operated in a single operation.

The second line contains $n$ integers $a_0,a_1,\ldots,a_{n-1}$ ($0 \leq a_i \lt m$) — the integers in the crystal balls.

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \leq n,m \leq 10^6$，$nm \leq 2 \cdot 10^6$，$1 \leq k \lt n$）—— 分别表示雕像的数量、水晶球中整数的上界，以及单次操作可处理的雕像数量。

第二行包含 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$（$0 \leq a_i \lt m$）—— 表示各水晶球中的整数。

If it is possible to perform zero or more operations so that $a_0=a_1=\ldots=a_{n-1}=0$, output the minimum number of operations required. Otherwise, output $-1$.

如果可以通过执行零次或多次操作使得 $a_0=a_1=\ldots=a_{n-1}=0$，则输出所需的最少操作次数；否则，输出 $-1$。

In the first example, Pak Chanek can do the following operations:

1. Do the $a_i := (a_i-1) \bmod m$ operation $3$ times for statues $1$, $2$, and $3$. Now $a=[8,7,1,2,0]$.
2. Do the $a_i := (a_i-1) \bmod m$ operation $1$ time for statues $3$, $4$, and $0$. Now $a=[7,7,1,1,8]$.
3. Do the $a_i := (a_i+1) \bmod m$ operation $2$ times for statues $4$, $0$, and $1$. Now $a=[0,0,1,1,1]$.
4. Do the $a_i := (a_i-1) \bmod m$ operation $1$ time for statues $2$, $3$, and $4$. Now $a=[0,0,0,0,0]$.

在第一个例子中，Pak Chanek 可执行以下操作：

1. 对雕像 $1$、$2$ 和 $3$ 各执行 $3$ 次 $a_i := (a_i-1) \bmod m$ 操作。此时 $a=[8,7,1,2,0]$。
2. 对雕像 $3$、$4$ 和 $0$ 各执行 $1$ 次 $a_i := (a_i-1) \bmod m$ 操作。此时 $a=[7,7,1,1,8]$。
3. 对雕像 $4$、$0$ 和 $1$ 各执行 $2$ 次 $a_i := (a_i+1) \bmod m$ 操作。此时 $a=[0,0,1,1,1]$。
4. 对雕像 $2$、$3$ 和 $4$ 各执行 $1$ 次 $a_i := (a_i-1) \bmod m$ 操作。此时 $a=[0,0,0,0,0]$。