B. Прогулка по Aллее
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На Главной Аллее в ЛКШ расположены $$$n$$$ лавочек, пронумерованных целыми числами от $$$1$$$ до $$$n$$$ слева направо. Также на Аллее есть $$$m$$$ торговых палаток, $$$i$$$-я ($$$1 \le i \le m$$$) из которых расположена около $$$s_i$$$-й лавочки.

Петя сейчас находится в начале Аллеи перед $$$1$$$-й лавочкой и он хочет дойти до $$$n$$$-й лавочки. Расстояние между последовательными лавочками Петя проходит за $$$1$$$ минуту. У него с собой есть рюкзак с бесконечным количеством вафель. Петя планирует есть вафли из рюкзака и покупать их в торговых палатках во время прогулки.

Петя ест вафли только находясь около лавочек, причём он съест вафлю, находясь около $$$i$$$-й ($$$1 \le i \le n$$$) лавочки тогда и только тогда, когда выполняется хотя бы одно из следующих условий:

  • Около $$$i$$$-й лавочки есть торговая палатка. Тогда Петя купит вафлю в торговой палатке и сразу съест её.
  • Петя ещё ни разу не ел вафлю. Тогда Петя возьмёт вафлю из рюкзака и сразу съест её.
  • После того, как Петя съел последнюю вафлю, прошло хотя бы $$$d$$$ минут. Иными словами, Петя не ел вафли около каждой из лавочек $$$i-1, i-2, \ldots, \max(i-d+1, 1)$$$. Тогда Петя возьмёт вафлю из рюкзака и сразу съест её.

Вы можете считать, что Петя не тратит время на то, чтобы съесть вафлю. Петя никогда не будет есть две или более вафли около одной лавочки.

Вы хотите минимизировать количество вафель, которые съест Петя в течении прогулки. Для этого вы попросите администрацию ЛКШ убрать ровно одну торговую палатку с Аллеи до того как Петя начнёт движение.

Определите минимальное возможное количество вафель, которые съест Петя в течении прогулки. Также найдите количество торговых палаток, таких что если убрать одну из них, Петя съест минимальное возможное число вафель.

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

В первой строке дано одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке даны три целых числа $$$n$$$, $$$m$$$ и $$$d$$$ ($$$2 \le d \le n \le 10^9$$$, $$$2 \le m \le \min(10^{5}, n)$$$) — количество лавочек, количество торговых палаток и параметр $$$d$$$ из условия, соответственно.

Во второй строке даны $$$m$$$ целых чисел $$$s_1, s_2, \ldots, s_m$$$ ($$$1 \le s_i \le n$$$) — номера лавочек, около которых расположены торговые палатки. Гарантируется, что $$$s_{i} < s_{i+1}$$$ для всех $$$1 \leq i \leq m - 1$$$.

Гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите два целых числа — минимальное количество вафель, которые съест Петя, если будет убрана ровно одна торговая палатка, и количество торговых палаток, таких что если убрать одну из них, Петя съест минимальное возможное число вафель.

Пример
Входные данные
8
6 2 2
2 5
8 3 2
3 5 8
10 4 9
2 8 9 10
30 5 8
6 8 15 24 29
30 5 8
6 8 12 20 27
8 8 3
1 2 3 4 5 6 7 8
2 2 2
1 2
1000000000 3 20000000
57008429 66778899 837653445
Выходные данные
3 1
4 1
4 4
6 4
5 2
7 7
1 1
51 1
Примечание

В первом наборе данных $$$n=6$$$, $$$m=2$$$, $$$d=2$$$ и $$$s=[2, 5]$$$. При таком расположении торговых палаток Петя съест $$$4$$$ вафли в течении прогулки (обратите внимание, что необходимо убрать ровно одну торговую палатку; этот случай разобран только для того, чтобы показать как Петя принимает решение о том, следует ли съесть вафлю у очередной лавочки):

  • Около $$$1$$$-й лавочки Петя съест вафлю из рюкзака, так как он ещё ни разу не ел вафлю.
  • Около $$$2$$$-й лавочки Петя съест вафлю из торговой палатки, так как около этой лавочки есть торговая палатка.
  • Около $$$3$$$-й лавочки Петя не будет есть вафлю, так как с момента как он съел вафлю прошла $$$1<d$$$ минута.
  • Около $$$4$$$-й лавочки Петя съест вафлю, так как с момента как он съел вафлю прошло $$$2\ge d$$$ минуты.
  • Около $$$5$$$-й лавочки Петя съест вафлю из торговой палатки, так как около этой лавочки есть торговая палатка.
  • Около $$$6$$$-й лавочки Петя не будет есть вафлю, так как с момента как он съел вафлю прошла $$$1<d$$$ минута.

Если убрать $$$1$$$-ю торговую палатку, то Петя съест $$$3$$$ вафли (около лавочек $$$1$$$, $$$3$$$ и $$$5$$$). Если же убрать $$$2$$$-ю торговую палатку, то Петя съест $$$4$$$ вафли (около лавочек $$$1$$$, $$$2$$$, $$$4$$$ и $$$6$$$).

Таким образом, минимальное количество вафель, которые съест Петя — $$$3$$$; существует только одна палатка, убрав которую можно достигнуть такого количества вафель.

Во втором наборе входных данных

  • если убрать $$$1$$$-ю или $$$2$$$-ю палатку, то Петя съест $$$5$$$ вафель около лавочек $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$, $$$8$$$;
  • если убрать $$$3$$$-ю палатку, то Петя съест $$$4$$$ вафли около лавочек $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$.

В третьем наборе входных данных Петя съест $$$4$$$ вафли вне зависимости от вашего выбора.

Обратите внимание, что Петя не заинтересован в минимизации количества вафель, которые он съест, поэтому он будет есть вафли строго в соответствии с правилом, описанным в условии.