现在 Dmitry 有一个会话,他必须通过 $$$n$$$ 考试。会话从 $$$1$$$ 天开始,持续 $$$d$$$ 天。第 $$$i$$$ 考试将于 $$$a_i$$$ ($$$1 \le a_i \le d$$$) 当天举行,所有 $$$a_i$$$ 均不同。
示例,其中 $$$n=3$$$、$$$d=12$$$、$$$a=[3,5,9]$$$。橙色——考试日。在第一次考试之前,Dmitry 将休息 $$$2$$$ 天,在第二次考试之前,他将休息 $$$1$$$ 天,在第三次考试之前,他将休息 $$$3$$$ 天。
对于课程安排,Dmitry 考虑了一个特殊值 $$$\mu$$$ — 所有考试的考试前休息时间中最小的一个。例如,对于上图,$$$\mu=1$$$。换句话说,对于日程安排,他精确地计算了 $$$n$$$ 数字 - 在考试 $$$i-1$$$ 和 $$$i$$$ 之间休息了多少天(对于 $$$i=0$$$ 课程开始和考试 $$$i$$$ 之间)。然后它找到 $$$\mu$$$ — 这些 $$$n$$$ 数字中的最小值。
德米特里相信他可以改进会议的安排。他可能会要求更改一项考试的日期(更改 $$$a_i$$$ 的任意值)。帮助他更改日期,使所有$$$a_i$$$保持不同,并且$$$\mu$$$的值尽可能大。
例如,对于上面的时间表,对于 Dmitry 来说,将第二次考试移到课程的最后是最有利的。新的时间表将采用以下形式:
现在考试前的休息时间等于$$$[2,2,5]$$$。所以,$$$\mu=2$$$。
Dmitry 可以保持提议的时间表不变(如果无法移动一项考试以改善情况)。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入测试用例的数量。测试用例的描述如下。
在每个案例之前的测试中写入一个空行。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le d \le 10^9$$$) - 分别是考试次数和课程长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le d, a_i < a_{i+1}$$$),其中第 $$$i$$$ 数字表示第 $$$i$$$ 考试的日期。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果 Dmitry 可以将任何一项考试移至任意一天,则输出 $$$\mu$$$ 的最大可能值。 $$$a_i$$$ 的所有值应保持不同。
示例
输入 #1
9 3 12 3 5 9 2 5 1 5 2 100 1 2 5 15 3 6 9 12 15 3 1000000000 1 400000000 500000000 2 10 3 4 2 2 1 2 4 15 6 11 12 13 2 20 17 20
输出 #1
2 1 1 2 99999999 3 0 1 9
注意
第一个样本在语句中解析。
第二个样本的最佳时间表更改之一:
初始时间表。
新时间表。
在第三个示例中,我们需要将考试从 $$$1$$$ 转移到 $$$4$$$ 到 $$$100$$$ 之间的任何一天。
在第四个示例中,时间表的任何更改只会减少 $$$\mu$$$,因此时间表应保持原样。
在第五个示例中,我们需要将考试从 $$$1$$$ 转移到 $$$100000000$$$ 到 $$$300000000$$$ 之间的任何一天。
第六个样本的最佳时间表更改之一:
初始时间表。
新时间表。
在第七个样本中,每天都是考试日,并且不可能重新安排日程。