CF1993C.Light Switches

一栋公寓楼里面有 $n$ 个房间，初始时每个房间的灯都是关的。为了更好地对房间里的灯进行控制，房东计划在不同时间给每个房间安装芯片。具体地，房东给每个房间安装芯片的时刻可以用包含 $n$ 个整数的数组 $a$ 来表示，其中第 $i$ 个元素 $a_i$ 表示房东给第 $i$ 个房间安装芯片的时刻。

一旦某个房间被安装上了芯片，这个房间里面的灯的状态每隔 $k$ 分钟就会发生一次变化，也就是说，安装商芯片的这一时刻起，这个房间里面的灯会先被点亮，$k$ 分钟后被熄灭，$k$ 分钟后再被点亮，如此循环往复。形式化的来讲，对于第 $i$ 个房间的灯，它的状态会在第 $a_i,a_i+k,a_i+2k,\dots$ 分钟发生变化。

现在请你求出所有房间的灯都被点亮的最小时刻，或者报告不存在所有房间的灯都被点亮的时刻。

本题包含多组数据。

第一行输入一个整数 $T$，表示数据组数。

对于每组数据，第一行输入两个整数 $n,k$，分别表示房间个数和灯的状态发生变化的时间间隔。第二行输入 $n$ 个整数，第 $i$ 个整数表示房东给第 $i$ 个房间安装芯片的时刻 $a_i$。

对于每组数据，如果不存在所有房间的灯都被点亮的时刻，输出一行 $-1$，否则输出一行一个整数，表示所有房间的灯都被点亮的最小时刻（单位为分钟）。

输入输出样例

见下文 输入 #1 和 输出 #1。

样例 #1 解释

对于第一组数据，可以发现在第 $5$ 分钟所有的灯都是开着的。

对于第二组数据，第一个房间的灯被点亮的时刻为 $2,3,4,8,9,10,14\dots$，而第四个房间的灯被点亮的时刻为 $5,6,7,11,12,13,17,\dots$，可以发现这两个房间的灯无论什么时刻都不可能同时被点亮。

对于第三组数据，各个房间的灯在前 $10$ 分钟的状态如下表所示：

时刻（分钟）	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$1$ 号房间的灯	关	关	开	开	开	关	关	关	开	开
$2$ 号房间的灯	关	关	关	开	开	开	关	关	关	开
$3$ 号房间的灯	关	关	关	关	关	关	关	开	开	开
$4$ 号房间的灯	关	关	关	关	关	关	关	关	开	开

因此，所有房间的灯都被点亮的最小时刻为 $10$。

对于所有数据：

• $1\leqslant T\leqslant 10^4$。
• $1\leqslant k\leqslant n\leqslant 2\times 10^5$，$\sum n\leqslant 2\times 10^5$。
• $1\leqslant a_n\leqslant 10^9$。

Translated by Eason_AC。