침입자 따돌리기

Amiria는 신중한 인터넷 사용자이므로 자신의 계정에 이중 인증을 설정하고 있다. 그녀는 보안 키를 노릴 수 있는 침입자를 따돌리기 위한 추가 예방책으로 특별한 종류의 보안 키를 사용하고 있다. Amiria의 보안 키를 활성화하려면 코드가 필요하다. 코드를 입력하려면 번호가 적힌 회전판을 맞춰야 하며, 이는 번호식 자물쇠와 비슷하다.

Amiria의 보안 키에는 $\mathbf{W}$개의 회전판이 일렬로 배치되어 있다. 각 회전판에는 $1$부터 $\mathbf{N}$까지의 수가 순서대로 적혀 있다. 회전판을 한 번 돌리면 사용자는 현재 표시된 정수를 다음 정수나 이전 정수로 바꿀 수 있다. 회전판의 수는 끝에서 처음으로 순환한다. 즉, $\mathbf{N}$ 다음의 수는 $1$이고, $1$ 이전의 수는 $\mathbf{N}$이다.

숨겨진 비밀번호는 없다. Amiria의 보안 키를 활성화하려면 회전판을 움직여 표시된 수의 수열이 팰린드롬이 되게 해야 한다. 즉, 수열을 왼쪽에서 오른쪽으로 읽은 결과와 오른쪽에서 왼쪽으로 읽은 결과가 같다. 침입자의 진행을 늦추기 위해 Amiria는 회전판이 $\mathbf{D}$씩만 회전하도록 보안 키를 조작했다. 즉, 한 번의 연산으로 현재 $x$을 표시하는 회전판이 적절한 순환 처리를 적용하여 $x - \mathbf{D}$ 또는 $x + \mathbf{D}$을 표시하게 할 수 있다. 즉, $x - \mathbf{D} \lt 1$이면 연산 후 실제로 표시되는 수는 $x - \mathbf{D} + \mathbf{N}$이고, $x + \mathbf{D} \gt \mathbf{N}$이면 실제로 표시되는 수는 $x + \mathbf{D} - \mathbf{N}$이다.

Amiria는 이 시스템이 자신의 보안 키를 사용하려는 침입자의 진행을 얼마나 늦출지 확인하고 싶어 한다. 회전판의 수와 각 회전판에 현재 표시된 수가 주어질 때, 표시된 수의 수열을 팰린드롬으로 만드는 데 필요한 최소 연산 횟수를 구하거나, 그렇게 하는 것이 불가능하다고 보고하라.

제한

시간 제한: 5초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{D} \le \mathbf{N} - 1$. 모든 $i$에 대해 $1 \le \mathbf{X_i} \le \mathbf{N}$.

테스트 세트 1 (결과 공개)

$2 \le \mathbf{W} \le 5$. $2 \le \mathbf{N} \le 5$.

테스트 세트 2 (결과 공개)

$2 \le \mathbf{W} \le 1000$. $2 \le \mathbf{N} \le 10^9$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 각 테스트 케이스의 첫 번째 줄에는 $3$개의 정수 $\mathbf{W}$, $\mathbf{N}$, $\mathbf{D}$가 주어진다. 이들은 각각 Amiria의 보안 키에 있는 회전판의 수, 각 회전판에 표시되는 정수의 수, 그리고 Amiria가 모든 회전판에 설정한 고정 증분이다. 테스트 케이스의 두 번째 줄에는 $\mathbf{W}$개의 정수 $\mathbf{X_1}, \mathbf{X_2}, \dots, \mathbf{X_W}$가 주어지며, 여기서 $\mathbf{X_i}$는 왼쪽에서 오른쪽으로 $i$번째 회전판에 현재 표시된 수이다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 표시된 수의 수열을 팰린드롬으로 만드는 데 필요한 최소 연산 횟수이다. 허용된 연산을 통해 표시된 수의 수열을 팰린드롬으로 만들 방법이 없다면, 대신 $y$는 IMPOSSIBLE이어야 한다.

예제 케이스 #1에서는 첫 번째와 네 번째 회전판에 덧셈 연산을 한 번씩 적용하고, 다섯 번째 회전판에 뺄셈 연산을 한 번 적용하여 $3$번의 연산으로 수열을 팰린드롬인 $5 ~ 4 ~ 5 ~ 4 ~ 5$로 만들 수 있다. 이보다 적은 연산으로 수열을 팰린드롬으로 만들 방법은 없다.

예제 케이스 #2에서는 수열이 이미 팰린드롬이므로 아무 연산도 필요하지 않다.

예제 케이스 #3에서는 수열이 팰린드롬이 되려면 두 수가 같아야 한다. 회전판의 값은 $2$씩만 움직일 수 있고 현재 두 수의 홀짝성이 서로 다르므로, 그렇게 할 수 없다.