연속 풀이 일수

최근 경쟁 프로그래밍 사이트 Deltaforces가 사용자 프로필에 새로운 시각 정보를 많이 추가했다. 그중 하나가 최대 연속 일수이며, 적어도 한 문제를 푼 날이 연속으로 이어지는 최대 일수다. 프로필에 표시된 최대 연속 일수가 실제 훈련량을 잘 반영하지 못해서, 시간대를 바꾸면 연속 일수를 늘릴 수 있는지 생각해 본다.

$n$을 푼 문제 수, $i$번째 문제를 푼 시각을 $a_i$라고 하자. 시간대는 $0$부터 $m-1$까지 $m$개가 있다. 기본 시간대는 $0$이다. 시간대를 $t$로 바꾸면 모든 타임스탬프가 동시에 $t$만큼 증가한다. 즉 시각 $a_i$에 푼 문제는 모든 $i$에 대해 시각 $a_i + t$에 푼 것으로 간주된다.

시각 $x$에 푼 문제는 $\lfloor \frac{x}{m} \rfloor$번째 날에 센다. 여기서 $\lfloor v \rfloor$는 $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 < a_2 < \dotsb < a_n \le 10^9$).

모든 테스트 케이스의 $n$ 합은 $2 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 최대 연속 일수 $s$와 그것을 달성하는 시간대 $t$를 두 정수로 출력한다 ($1 \le s \le n$; $0 \le t < m$). 답이 여럿이면 그중 아무거나 출력하면 된다.

첫 번째 예제에서 시간대 $2$를 고르면 타임스탬프가 $2, 5, 10, 26$으로 바뀐다. 이는 날 $0, 0, 1, 2$에 해당하며 3일 연속이다. 시간대 $3$, $4$, $5$도 같은 답을 준다.

두 번째 예제에서 시간대 $5$를 고르면 타임스탬프가 $37$과 $40$이 되어 날 $3$과 $4$에 해당한다. 시간대 $6$과 $7$도 가능하다.

세 번째 예제에는 시간대가 하나뿐이며, 최대 연속 일수는 $5$다.

네 번째 예제에서는 많은 문제를 짧은 기간에 풀었기 때문에 $2$일 연속을 넘을 수 없다.