题目描述

最近，著名的算法竞赛网站 Deltaforces 在用户资料页中加入了许多新的可视化信息。其中有一项是最长连续解题天数：即连续若干天中，每天至少解决一道题时，这段连续天数的最大长度。

你觉得资料页上显示的最长连续解题天数并不能准确反映自己的训练强度，于是想到：如果修改个人资料中的时区，能否让最长连续解题天数变得更长？

形式化地说，假设你一共解决了 $n$ 道题，第 $i$ 道题的提交时间为 $a_i$。

共有 $m$ 个时区，编号为 $0,1,\ldots,m-1$，默认时区为 $0$。如果你把时区改成 $t$，那么所有提交的时间戳都会同时增加 $t$，即原本在时刻 $a_i$ 解决的题，会被视为在时刻

解决。

在时刻 $x$ 解决的题，被认为是在第

天解决的。其中 $\lfloor v\rfloor$ 表示不超过 $v$ 的最大整数。

为了显示最长连续解题天数，Deltaforces 会找到两个整数 $l,r$，使得从第 $l$ 天到第 $r$ 天的每一天都至少解决了一道题，并令 $r-l+1$ 尽可能大。此时显示的最长连续解题天数就是 $r-l+1$。

请你选择一个时区，使最长连续解题天数尽可能大。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据组数：

对于每组测试数据：

• 第一行包含两个整数 $n,m$，分别表示已解决题目的数量和时区数量：

• 第二行包含 $n$ 个严格递增的整数

表示各题的提交时间：

保证所有测试数据中的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每组测试数据，输出两个整数 $s,t$：

• $s$ 表示能够得到的最大连续解题天数；
• $t$ 表示任意一个能够达到该最大值的时区。

要求

样例

5
4 10
0 3 8 24
2 10
32 35
10 1
0 1 3 4 5 6 7 10 11 12
10 24
0 1 3 4 5 6 7 10 11 12
8 24
26 71 101 147 181 201 244 268

3 2
2 5
5 0
2 12
4 15

样例说明

第一组数据中，选择时区 $2$ 后，提交时间变为 $2,5,10,26$，分别属于第 $0,0,1,2$ 天，因此得到连续 $3$ 天的记录。时区 $3,4,5$ 也可以得到同样的答案。

第二组数据中，在时区 $5$ 下，两次提交时间变成 $37$ 和 $40$，对应第 $3$ 天和第 $4$ 天，因此连续天数为 $2$。时区 $6,7$ 也可以。

第三组数据中只有一个时区，最大连续解题天数为 $5$。

第四组数据中，虽然解决了很多题，但这些题集中在较短的时间段内，因此无法得到超过 $2$ 天的连续记录。