Overgrown-Puzzled

여느 때와 다름없는 어느 날, 선우는 등굣길에서 이상한 토끼 니키를 만났다. 니키는 회중시계를 든 채 바쁘다는 말만 중얼거렸다.

니키를 따라가던 선우는 막다른 길에서 니키가 토끼굴로 들어가는 것을 보고, 잠시 망설이다가 토끼굴에 뛰어들었다.

시간이 얼마나 지났을까, 선우가 눈을 떠 보니 환상적인 장난감 나라의 거대한 도넛 위에 떨어져 있었다. 겉모습은 등굣길에 들고 가던 우유맛, 딸기맛, 초코맛 아이싱이 코팅된 도넛과 똑같이 생겼다. 거대 도넛은 원형으로 이어진 $n$개의 칸으로 이루어져 있고, 각 칸에는 0 이상 $n-1$ 이하의 정수 번호가 붙어 있다. 0번 칸에서 시계 방향으로 한 칸씩 $n$번 이동하면 $1$, $2$, ..., $n-1$, $0$번 칸이 순서대로 나온다.

니키는 거대 도넛 탐사의 규칙을 다음과 같이 설명하며 선우를 재촉했다.

• 선우는 맨 처음 거대 도넛 위 임의의 위치에 떨어진다. 니키는 처음에 선우와 같은 칸에 있다.
• 선우는 시계 방향 또는 반시계 방향으로 한 칸 움직일 수 있다. 선우는 최대 $M$번 움직일 수 있다.
• 선우가 움직인 직후 니키가 움직인다. 니키는 선우가 움직이기 전에 밟았던 칸과 자신이 지금 밟고 있는 칸의 아이싱 종류를 비교한다. 두 칸의 아이싱 색이 다를 때에만 선우가 움직인 방향과 같은 방향으로 한 칸 움직이고, 같으면 움직이지 않는다.
• 선우와 니키가 모두 움직인 뒤, 선우는 니키가 자신과 같은 칸에 있는지 확인할 수 있다. 선우와 니키 사이의 거리 등 다른 정보는 알 수 없다.
• 선우는 언제든지 자신이 처음 떨어진 칸의 번호를 말할 수 있다. 정답을 맞히면 니키가 선우를 새로운 세계로 데려갈 것이다.

선우는 이리저리 움직여 보며 자신의 위치를 파악하려 했지만, 준비 없이 토끼굴에 뛰어든 탓에 방법이 없었고 결국 첫 번째 퍼즐 해결에 실패했다.

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