조명 최적화

Onyaomale은 고속도로를 따라 설치된 가로등의 백열전구를 에너지 효율과 성능이 모두 더 뛰어난 LED 전구로 교체하는 프로젝트를 이끌고 있다. 그녀는 오래된 백열전구를 모두 빼는 것부터 시작했고, 이제 새로운 LED 전구를 설치하는 데 집중하고 있다. 새 전구가 더 강력하기 때문에, Onyaomale은 일부 가로등이 필요하지 않을 수도 있으며 그 가로등을 사용하지 않음으로써 에너지를 더욱 절약할 수 있다고 생각한다.

고속도로를 서쪽에서 동쪽으로 이어지는 길이 $\mathbf{M}$미터의 직선으로 모델링한다. $x$번째 미터는 고속도로의 서쪽 끝에서 동쪽으로 $x$미터 떨어진 지점이다. 가로등이 $x$번째 미터에 있고 조명 반경이 $\mathbf{R}$미터인 전구를 그 가로등에 설치하면, 해당 가로등은 $\max(0, x - \mathbf{R})$번째 미터에서 시작하여 $\min(\mathbf{M}, x + \mathbf{R})$번째 미터에서 끝나는 고속도로 구간을 양 끝점을 포함하여 밝힌다. Onyaomale은 고속도로의 모든 지점이 적어도 하나의 전구로 밝혀지도록 전구를 설치해야 한다. 여기에는 고속도로 끝점에서 정수 미터만큼 떨어져 있지 않은 지점도 밝혀야 한다는 점에 유의하라. 전구가 설치되지 않은 가로등은 아무것도 밝히지 않는다.

미터 단위의 고속도로 길이 $\mathbf{M}$, 새 전구의 조명 반경 $\mathbf{R}$, 모든 가로등의 위치가 주어질 때, 고속도로 전체를 밝히기 위해 Onyaomale이 설치해야 하는 최소 전구 수를 구하거나, 그렇게 하는 것이 불가능하다고 보고하라.

제한

시간 제한: 10초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{M} \le 10^9$. $1 \le \mathbf{R} \le 10^9$. $0 \le \mathbf{X_1}$. 모든 $i$에 대해, $\mathbf{X_i} \lt \mathbf{X_{i+1}}$. $\mathbf{X_N} \le \mathbf{M}$.

테스트 세트 1 (Visible Verdict)

$1 \le \mathbf{N} \le 10$.

테스트 세트 2 (Visible Verdict)

$1 \le \mathbf{N} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 세 정수 $\mathbf{M}$, $\mathbf{R}$, $\mathbf{N}$이 주어지며, 각각 미터 단위의 고속도로 길이, 미터 단위의 전구 조명 반경, 가로등의 수를 나타낸다. 테스트 케이스의 두 번째 줄에는 가로등이 위치한 고속도로상의 미터 지점을 나타내는, 정렬된 $\mathbf{N}$개의 정수 $\mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_N}$이 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 가능한 경우 고속도로 전체를 밝히기 위해 Onyaomale이 설치해야 하는 최소 전구 수이다. 현재 가로등을 사용하여 고속도로 전체를 밝힐 방법이 없다면, 대신 $y$는 IMPOSSIBLE이어야 한다.

예제 케이스 #1에서 Onyaomale은 가장 서쪽과 가운데 가로등에만 전구를 설치하고 가장 동쪽의 가로등은 사용하지 않음으로써 고속도로 전체를 밝힐 수 있다. 이 두 가로등이 $[0, 5]$와 $[4, 10]$를 비추므로 고속도로 전체($[0, 10]$)가 밝혀진다.

예제 케이스 #2에서 Onyaomale의 가로등 배치는 예제 케이스 #1와 같지만, 전구의 성능이 더 약하다. 이 경우 그녀가 고속도로 전체를 밝힐 방법은 없다. 특히 모든 가로등을 켜더라도 $4$번째 미터와 $5$번째 미터 사이의 중간 지점은 여전히 밝혀지지 않는다.

예제 케이스 #3에서 Onyaomale은 예제 케이스 #2와 비교해 $3$번째 미터에 가로등이 하나 더 있으며, 다른 모든 조건은 같다. 이 경우 고속도로 전체를 밝히는 유일한 방법은 모든 가로등에 전구를 설치하는 것이다.