← 返回题目列表

Codeforces · 1993/C

C. 灯开关

中文机器翻译题面 查看原题

有一套公寓,由 $$$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$$$。