문제

ALOHA의 유구한 전통에 따라, ALOHA의 차기회장은 항상 후보 명 간의 가위바위보 토너먼트로 결정된다.

하지만 가위바위보는 비길 확률이 1/3이나 되는 게임이기 때문에, 다양한 패를 사용해서 비길 확률을 낮춘 RPS-을 사용한다.

RPS-의 규칙은 다음과 같다.

• RPS-에는 가지의 패가 존재한다 (은 홀수). 편의상 이를 부터 까지의 번호로 나타내자.
• 인 에 대해, 패 는 패 한테 이긴다. 편의상 패 와 패 은 동일하다고 가정하자.
• 패 가 패 를 이긴다면, 패 는 패 한테 진다.
• 패 와 패 는 비긴다.

예를 들면, 아래는 RPS-의 승패 결정 방식이다.

차기회장을 결정짓는 가위바위보 토너먼트는 아래와 같이 진행된다.

• 명의 후보에게 번부터 번까지의 서로 다른 번호가 부여된다.
• 번 후보는 항상 패 만을 내야 한다.
• 대진표의 맨 밑, 즉 초기 배치는 현재 회장이 자유롭게 결정한다.
• 그 뒤, 토너먼트 대진표는 아래와 같은 방식으로 만들어진다.
  • 만약 남은 사람 이 홀수라면, 맨 오른쪽 사람이 부전승으로 올라간다. 이후, 남은 명에 대해 아래 짝수인 경우를 따른다.
  • 만약 남은 사람 이 짝수라면, 명의 사람들에 대해 앞에서부터 명씩 짝지은 뒤, RPS- 대결을 통해 명의 진출자를 결정한다.
  • 진출한 사람들의 상대적 순서는 변화하지 않는다.

예를 들면, 아래는 일 때 나올 수 있는 대진표이다.

올해의 회장인 effect2110은 차기회장으로 번 후보 mnx를 눈여겨보고 있는 중이라, mnx가 우승하는 배치를 만들기로 했다.

effect2110을 위해 mnx가 우승하는 배치를 만들어주자!

입력

첫째 줄에 내년도 차기회장 후보 명이 주어진다. 은 홀수

출력

첫째 줄에 대진표의 초기 배치를 앞에서부터 공백으로 구분하여 출력한다.

단, mnx가 우승하는 배치가 존재하지 않는다면 을 대신 출력한다.