最近，著名的编程竞赛网站 Deltaforces 在用户个人资料中增加了很多新的可视化信息。其中之一是“最大连续打卡天数”——即连续至少解决一道问题的最大天数。你认为个人资料中的最大连续打卡天数并不能准确反映你的训练成果。因此，你产生了一个想法：如果你能更改个人资料中的时区，是否可以增加最大连续打卡天数呢？

我们将此设定形式化如下。假设你解决了 $n$ 道题目，第 $i$ 道题是在时间 $a_i$ 解决的。共有 $m$ 个时区，编号从 $0$ 到 $m-1$。默认时区为 $0$。如果你决定将时区更改为 $t$，则所有题目的提交时间戳都会增加 $t$：即对于所有 $i$，在时间 $a_i$ 解决的题目现在被视为在时间 $a_i + t$ 解决。

在时间 $x$ 解决的题目被视为在第 $\lfloor \frac{x}{m} \rfloor$ 天解决。这里 $\lfloor v \rfloor$ 表示向下取整到小于或等于 $v$ 的最大整数。

为了显示最大连续打卡天数，Deltaforces 会寻找满足以下条件的 $l$ 和 $r$：你在第 $l, l+1, \dots, r$ 天的每一天都至少解决了一道题目，且 $r-l+1$ 尽可能大。此时，你的最大连续打卡天数显示为 $r-l+1$。

请找出通过选择某个时区所能达到的最大连续打卡天数。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 2 \cdot 10^5$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ —— 已解决题目的数量和时区的数量 ($1 \le n \le 2 \cdot 10^5$; $1 \le m \le 10^9$)。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 你解决题目的时间戳，按时间顺序排列 ($0 \le a_1 < a_2 < \dots < a_n \le 10^9$)。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出两个整数 $s$ 和 $t$ —— 最大连续打卡天数以及实现该天数的任意一个时区 ($1 \le s \le n; 0 \le t < m$)。

样例

输入 1

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

输出 1

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$ 天。时区 $6$ 和 $7$ 也同样有效。

在第三个样例测试用例中，只有一个时区存在，你的最大连续打卡天数为 $5$。

在第四个样例测试用例中，你虽然解决了很多题目，但它们是在很短的时间内完成的，因此你无法获得超过 $2$ 天的连续打卡。