You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

你的生日是 $7$ 月 $21$ 日，刚好是 $\color{SkyBlue}\text{Inaba Meguru}$ 后一天。绫地同学给你送来了一个好玩的游戏机（迫真。

题目描述

这个游戏机是这样的，上面有 $n$ 个非负整数排成一圈，数字的范围为 $[0,m-1]$。每次你可以同时把连续的 $k$ 个数同时上拨或下拨。

• 一个数原来为 $x$。上拨会变成 $(x+1)\bmod m$。
• 一个数原来为 $x$。下拨会变成 $(x+m-1)\bmod m$。

给定一个现有的状态，你想要把所有数归 $0$ 至少需要多少步？或者报告不可能。

输入格式

本题单点有多组测试数据。

第一行一个正整数 $T$ 表示测试组数。

对于每组数据，第一行三个正整数表示 $n,m,k$。第二行长度为 $n$ 的数组 $a_i$ 表示这个玩具的初始状态。

输出格式

每组数据，如果可以输出最小操作数，否则输出 $-1$。

测试样例

样例 $1$ 解释

对于样例组 1，一种可能的操作如下：

• $[8,1,4,5,0]$（初始状态）；
• $[8,7,1,2,0]$（下拨三步）；
• $[7,7,1,1,8]$（下拨一步）；
• $[7,7,0,0,7]$（下拨一步）；
• $[0,0,0,0,0]$（上拨两步）。

总共 $3+1+1+2=7$ 步。

样例 $2,3,4,5$ 解释

这些样例依次满足测试点 $1,3,7,9$ 的性质。

数据范围

对于所有数据：$k<n$，$n,m\leq 10^6$，$\sum n,\sum m\leq 10^7$，$\sum nm\leq 10^8$。