소 화재 대피 훈련

$N$마리의 소($3 \le N \le 250$)가 모닥불 주위에 완벽한 원을 이루고 앉아 있습니다. 소들은 편의상 $1$번부터 $N$번까지 번호가 매겨져 있고, 의자도 마찬가지로 $1$번부터 $N$번까지 번호가 매겨져 있습니다. 처음에 $i$번 소는 $i$번 의자에 앉아 있습니다.

한 이야기가 끝난 뒤, 농부 존은 "소 화재 대피 훈련"을 제안합니다.

소 화재 대피 훈련에서는 한 번에 한 마리의 소만 원을 따라 이동합니다. $i$번 소의 차례가 되면, 그 소는 일어나서 지금 앉아 있던 의자에서 시계 방향으로 $i$칸 떨어진 의자로 이동합니다. (예를 들어 $3$번 소의 차례라면, 그 소는 지금 있는 자리에서 시계 방향으로 세 칸 이동합니다.)

$i$번 소가 새 의자에 도착하면, 그 자리에 앉아 있는 소의 어깨를 두드립니다. 두드림을 받은 소는 자리를 비워 주기 위해 일어나고 $i$번 소가 그 자리에 앉으며, 방금 일어난 소가 다음 차례가 되어 같은 방식으로 이동합니다.

이 과정은 다음 두 경우 중 하나가 일어날 때까지 계속됩니다.

어떤 소가 비어 있는 의자에 도착한다.
어떤 소가 두 번째로 이동하도록 요청받는다. 즉, 이미 한 번 이동했던 소가 다시 어깨를 두드림 받는다.

$1$번 소가 항상 가장 먼저 이동하므로, 비어 있는 의자는 언제나 $1$번 소가 원래 앉아 있던 의자입니다.

정수의 성질 덕분에 훈련은 대개 일찍 끝나므로, 모든 소가 참여하는 경우는 드뭅니다. 마지막으로 이동한 소(비어 있는 $1$번 의자에 앉아서 훈련을 끝내든, 이미 이동한 적이 있는 소의 어깨를 두드려서 끝내든)가 특별한 상으로 부드러운 봄풀을 받습니다.

어떤 소가 이 상을 받게 될지 농부 존이 미리 알 수 있도록 도와주세요.

예를 들어 다섯 마리의 소가 모닥불 주위에 앉아 있다고 합시다. 아래에서 *는 비어 있는 의자를 나타냅니다.

  2   -   3
 (         )
  1 - 5 - 4

먼저 $1$번 소가 한 칸 이동하여 $2$번 소의 어깨를 두드리고, $2$번 소가 일어납니다.

    2
 1   -   3
 (         )
  * - 5 - 4

$2$번 소가 두 칸 이동하여 $4$번 소의 어깨를 두드리고, $4$번 소가 이동을 시작합니다.

  1  -    3
 (         )
  * -  5 - 2
          4

$4$번 소가 네 칸 이동하여 $3$번 소의 어깨를 두드립니다.

             3
  1   -    4
 (         )
  * -  5 - 2

마지막으로 $3$번 소가 세 칸 이동하여 비어 있는 $1$번 의자에 도착하고, 훈련이 끝납니다.

  1   -    4
 (         )
  3 -  5 - 2

$3$번 소가 다른 소들의 박수와 환호 속에서 부드러운 봄풀을 상으로 받습니다.

소 화재 대피 훈련

문제

입력

출력