有一套公寓,由 $$$n$$$ 个房间组成,每个房间的灯最初都是关闭的。
为了控制这些房间的灯光,公寓的主人决定在房间里安装芯片,这样每个房间就只有一个芯片,并且芯片安装的时间不同。具体来说,这些时间由数组 $$$a_1, a_2, \ldots, a_n$$$ 表示,其中 $$$a_i$$$ 是第 $$$i$$$ 个房间安装芯片的时间(以分钟为单位)。
一旦安装了芯片,它就会每隔 $$$k$$$ 分钟更改房间的灯光状态 — 它会打开灯 $$$k$$$ 分钟,然后在接下来的 $$$k$$$ 分钟内关闭灯,然后在接下来的 $$$k$$$ 分钟内重新打开灯,依此类推。换句话说,芯片在第 $$$i$$$ 个房间的 $$$a_i$$$、$$$a_i + k$$$、$$$a_i + 2k$$$、$$$a_i + 3k$$$、$$$\ldots$$$ 分钟改变灯光状态。
公寓内所有房间的灯最早打开的时刻是几点?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$)——公寓的房间数和筹码的周期。
第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 安装芯片的时刻。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 问题的答案(以分钟为单位)。如果没有所有房间的灯都打开的时刻,则打印$$$-1$$$。
示例
输入 #1
9 4 4 2 3 4 5 4 3 2 3 4 5 4 3 3 4 8 9 3 3 6 2 1 1 1 1 7 5 14 34 6 25 46 7 17 6 5 40 80 99 60 90 50 6 5 64 40 50 68 70 10 2 1 1 1000000000
输出 #1
5 -1 10 8 1 47 100 -1 -1
注意
在第一个测试用例中,所有灯都会在 $$$5$$$ 分钟内亮起,而没有任何灯被芯片关闭。答案是$$$5$$$。
在第二个测试用例中,由于 $$$k=3$$$,$$$1$$$-st 灯将在第 $$$2, 3, 4, 8, 9, 10, 14, \ldots$$$ 分钟亮起;同时,第 $$$4$$$ 灯将在 $$$5, 6, 7, 11, 12, 13, 17, \ldots$$$ 分钟亮起。这两个序列没有任何共同的编号,因此它们永远不会同时出现。
在第三个测试用例中,可以看到$$$1$$$-st和$$$2$$$-nd灯将在$$$6$$$和$$$7$$$分钟关闭,但芯片将在$$$9$$$和$$$10$$$分钟重新打开它们。第 $$$3$$$ 和第 $$$4$$$ 灯也会在 $$$10$$$ 分钟亮起,所以答案是 $$$10$$$。