D. Дневная серия
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Deltaforces, известный сайт соревновательного программирования, добавил много новой визуальной информации в профили пользователей. В частности, есть максимальная дневная серия — максимальное количество дней подряд с хотя бы одной решенной задачей. Вы решили, что максимальная дневная серия в вашем профиле не отражает точно ваши усилия в тренировке. Поэтому у вас возникла мысль — а что, если бы вы могли изменить часовой пояс в своем профиле, чтобы увеличить максимальную дневную серию?

Давайте формализуем эту ситуацию следующим образом. Предположим, что вы решили $$$n$$$ задач, и $$$i$$$-я задача была решена во времени $$$a_i$$$. Есть $$$m$$$ часовых поясов, пронумерованных от $$$0$$$ до $$$m - 1$$$. Часовой пояс по умолчанию — $$$0$$$. Если вы решите изменить свой часовой пояс на $$$t$$$, все временные метки решений увеличиваются на $$$t$$$: задача, решенная во времени $$$a_i$$$, теперь считается решенной во времени $$$a_i + t$$$, для всех $$$i$$$ одновременно.

Задача, решенная во времени $$$x$$$, считается решенной в день номер $$$\lfloor \frac{x}{m} \rfloor$$$. Здесь $$$\lfloor v \rfloor$$$ означает округление $$$v$$$ вниз до наибольшего целого числа, меньшего или равного $$$v$$$.

Для отображения максимальной дневной серии Deltaforces находит такие $$$l$$$ и $$$r$$$, что вы решили хотя бы одну задачу в каждый из дней $$$l, l+1, \ldots, 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, \ldots, a_n$$$ — различные временные метки ваших решений в хронологическом порядке ($$$0 \le a_1 \lt a_2 \lt \dotsb \lt a_n \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого тестового случая выведите два целых числа $$$s$$$ и $$$t$$$ — максимальную дневную серию и любой часовой пояс, достигающий этой серии ($$$1 \le s \le n$$$; $$$0 \le t \lt m$$$).

Пример
Входные данные
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$$$ дают тот же ответ.

Во втором примере тестового случая временные метки ваших решений равны $$$37$$$ и $$$40$$$ в часовом поясе $$$5$$$, что соответствует дням $$$3$$$ и $$$4$$$. Часовые пояса $$$6$$$ и $$$7$$$ также подходят.

В третьем примере тестового случая существует только один часовой пояс, и ваша максимальная дневная серия равна $$$5$$$.

В четвертом примере тестового случая вы решили много задач, но в короткий период времени, и вы не можете достичь более чем $$$2$$$-дневной серии.