Overgrown-Puzzled

여느 때와 다름없는 날, 선우는 학교 등굣길에 이상한 토끼 니키를 만나게 되었다. 니키는 회중시계를 든 채 바쁘다는 말만 중얼거릴 뿐이었다.

니키의 모습에 홀린 선우는 니키를 따라가기 시작하였다. 니키가 막다른 길에서 토끼굴로 들어가자, 선우는 조금 고민하다가 토끼굴에 뛰어들었다.

어느덧 시간이 지나 선우가 깨어보니 자기가 환상적인 장난감 나라 안 거대한 도넛 위로 불시착한 것을 깨달았다. 선우는 도넛의 겉모습을 확인해본 결과 등굣길에 들고 갔던 우유맛, 딸기맛, 초코맛 아이싱이 코팅된 도넛과 똑같은 모양인 것을 확인했다. 거대 도넛은 총 $n$개의 칸이 원형으로 붙어있으며 각 칸에는 $0$ 이상 $n-1$ 이하의 정수 번호가 붙어있다. 도넛의 $0$번 칸에서 시계 방향으로 $n$번 이동하면 $1$, $2$, ..., $n-1$, $0$번 칸이 순서대로 등장한다.

니키는 거대 도넛 탐사의 규칙을 아래와 같이 이야기하며 선우를 재촉하였다.

• 선우는 맨 처음 거대 도넛 위 임의의 위치로 불시착한다. 니키는 처음에 선우와 같은 칸에 있다.
• 선우는 시계 방향 또는 반시계 방향으로 한 칸 움직일 수 있다. 선우는 최대 $M$번 움직일 수 있다.
• 선우가 움직인 직후 니키가 움직인다. 니키는 선우가 움직이기 전에 밟은 칸과 현재 자신이 밟은 칸의 아이싱 종류를 비교하여 서로 다른 색일 때에만 선우가 움직인 방향과 동일하게 한 칸 움직인다. 만약 아이싱 종류가 같다면 니키는 움직이지 않는다.
• 선우와 니키가 움직이고 나서 선우는 니키가 자신과 같은 칸에 있는지 확인할 수 있다. 선우와 니키 사이의 거리 등 추가적인 정보는 알 수 없다.
• 선우는 언제든지 자신이 최초에 불시착한 칸의 번호를 이야기할 수 있다. 선우가 정답을 맞혔다면 니키가 새로운 세계로 선우를 데려갈 것이다.

선우는 이리저리 움직여 가며 자신의 위치를 파악해보려 했지만, 제대로 준비가 되지 않은 상태로 토끼굴에 뛰어드는 바람에 어찌할 방도가 없어서 결국 퍼즐 해결에 실패하였다.

선우는 니키의 토끼굴 너머 새로운 세계가 마음에 들었는지 도넛을 새로 만들어서 다시 토끼굴에 뛰어들기로 결심했다. 니키는 선우가 가져온 도넛의 크기에 따라 이동 횟수 제한을 다르게 이야기할 것이기 때문에 선우는 칸의 개수가 정확히 $N$개인 도넛을 만들어야 한다. 선우를 도와 니키의 첫 번째 퍼즐을 해결하는 프로그램을 작성하여라.