시계 둘레에서 춤추기

명망 높은 무도회장의 주인은 무도회장 바닥에 아름다운 원형 시계를 그렸고, 1부터 D까지 번호가 매겨진 D명의 무용수는 이제 말 그대로 "시계 둘레에서 춤추려고" 한다. 무용수들은 원을 이루어 서 있으며, 무용수 1은 원의 12:00 위치에 있고 나머지 무용수들은 번호가 증가하는 순서로 원을 따라 시계 방향으로 서 있다. 무용수의 수는 짝수이다.

춤은 N턴 동안 계속된다. i번째 턴에서(1부터 세기 시작한다) 다음과 같은 일이 일어난다:

• i가 홀수이면, 현재 12:00 위치에 있는 무용수가 시계 방향으로 다음에 있는 무용수와 자리를 바꾼다. 그런 다음 그 두 명을 지나, 시계 방향으로 다음에 있는 무용수 한 쌍이 자리를 바꾸고, 이 과정을 모든 무용수가 정확히 한 번의 자리 교환에 참여할 때까지 고리를 따라 시계 방향으로 계속한다.

• i가 짝수이면, 현재 12:00 위치에 있는 무용수가 반시계 방향으로 다음에 있는 무용수와 자리를 바꾼다. 그런 다음 그 두 명을 지나, 반시계 방향으로 다음에 있는 무용수 한 쌍이 자리를 바꾸고, 이 과정을 모든 무용수가 자리 교환에 참여할 때까지 고리를 따라 반시계 방향으로 계속한다.

예를 들어, 이 그림은 여덟 명이 추는 춤의 초기 상태와 두 턴을 보여 준다.

춤이 끝났을 때 무용수 번호 K의 양옆에는 어느 두 무용수가 있게 되는가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. D는 짝수이다. 1 ≤ K ≤ D.

작은 데이터 세트 (테스트 세트 1 - 공개)

4 ≤ D ≤ 10. 1 ≤ N ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

4 ≤ D ≤ $10^{8}$. 1 ≤ N ≤ $10^{8}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 D, K, N이 있는 한 줄로 구성되며, 각각 무용수의 총수, 무용수 중 한 명의 번호, 춤이 계속될 턴 수를 나타낸다.

각 테스트 케이스마다 Case #x: y z을 포함하는 한 줄을 출력한다. 여기서:

• x은 테스트 케이스 번호이다(1부터 시작한다).

• y은 춤이 끝났을 때 무용수 번호 K의 왼쪽(즉, 시계 방향으로 한 칸 떨어진 곳)에 서 있게 될 무용수의 번호이다.

• z은 춤이 끝났을 때 무용수 번호 K의 오른쪽(즉, 반시계 방향으로 한 칸 떨어진 곳)에 서 있게 될 무용수의 번호이다.

케이스 #1과 #2에 대해서는 위의 그림을 참고하라. 케이스 #1에서는 1턴 후 무용수 6이 무용수 3의 왼쪽에 있고, 무용수 4이 무용수 3의 오른쪽에 있다. 케이스 #2에서는 2턴 후 무용수 1이 무용수 4의 왼쪽에 있고, 무용수 7이 무용수 4의 오른쪽에 있다. 무용수의 관점에서 보고 있다는 점을 기억하라. 왼쪽과 오른쪽 대신 시계 방향과 반시계 방향으로 생각하면 도움이 될 수 있다.

케이스 #3에서는 여덟 턴 후 배치가 초기 배치와 같아지며, 무용수 2이 무용수 1의 왼쪽에 있고 무용수 4이 무용수 1의 오른쪽에 있다.