The Walkway

Description:

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$d$$$ ($$$2 \le d \le n \le 10^9$$$, $$$2 \le m \le \min(10^{5}, n)$$$) — the number of benches, the number of cookie sellers and the value of parameter $$$d$$$ from the statement, respectively.

The second line of each test case contains $$$m$$$ integers $$$s_1, s_2, \ldots, s_m$$$ ($$$1 \le s_i \le n$$$) — the locations of the cookie sellers. It is guaranteed that $$$s_{i} < s_{i+1}$$$ for all $$$1 \leq i \leq m - 1$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output:

For each test case print two integers — the minimum number of cookies that Petya can eat if exactly one cookie seller is removed, and the number of cookie sellers such that if one of them is removed, Petya will eat the minimum possible number of cookies.

Sample Input:

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

Sample Output:

3 1
4 1
4 4
6 4
5 2
7 7
1 1
51 1

Note:

In the first test case $$$n=6$$$, $$$m=2$$$, $$$d=2$$$ and $$$s=[2, 5]$$$. If no cookie seller is removed, then Petya will eat $$$4$$$ cookies during his walk (note that you have to remove exactly one cookie seller; this case is explained only to show how Petya decides whether to eat a cookie):

• Petya will eat a cookie near the $$$1$$$-st bench since he has not yet eaten a cookie.
• Petya will eat a cookie near the $$$2$$$-nd bench since there is a cookie seller near this bench.
• Petya will not eat a cookie near the $$$3$$$-rd bench since only $$$1<d$$$ minute passed since he ate a cookie.
• Petya will eat a cookie near the $$$4$$$-th bench since $$$2\ge d$$$ minutes passed since he ate a cookie.
• Petya will eat a cookie near the $$$5$$$-th bench since there is a cookie seller near this bench.
• Petya will not eat a cookie near the $$$6$$$-th bench since only $$$1<d$$$ minute passed since he ate a cookie.

If the $$$1$$$-st cookie seller is removed, Petya will eat $$$3$$$ cookies (near the benches $$$1$$$, $$$3$$$ and $$$5$$$). If the $$$2$$$-nd cookie seller is removed, Petya will eat $$$4$$$ cookies (near the benches $$$1$$$, $$$2$$$, $$$4$$$ and $$$6$$$).

Thus, the minimum number of cookies Petya will eat is $$$3$$$; there is only one cookie seller such that removing it results in minimizing the number of cookies Petya will eat.

In the second test case

• the removal of the $$$1$$$-st or the $$$2$$$-nd cookie seller results in Petya eating $$$5$$$ cookies near the benches $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$, $$$8$$$;
• the removal of the $$$3$$$-rd cookie seller results in Petya eating $$$4$$$ cookies near the benches $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$.

Note that the second integer you should output is the number of (that is, amount) cookie sellers, not the index of a cookie seller to remove. Thus, the answer to the second test case is 4 1 because there is only one cookie seller such that removing it results in Petya eating four cookies, which is the minimum possible.

In the third test case Petya will eat $$$4$$$ cookies no matter what cookie seller is removed.

Note that Petya is not interested in minimizing the number of cookies he will eat, so he eats cookies whenever it is possible under the rule from the statement.