시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB97292663.415%

문제

브루는 오렌지 섬으로 여행을 떠났다. 오렌지 섬에는 $N$개의 오렌지 나무가 서 있고, 이들은 각각 1번부터 $N$번까지의 번호가 붙어 있다.

브루는 섬의 1번 오렌지 나무에게 오렌지 섬의 역사에 관해 물었다. 1번 오렌지 나무는 아래와 같이 오렌지 섬의 역사를 읊어 주었다.

"태초에, $N$ 그루의 오렌지 나무는 오렌지를 하나도 가지고 있지 않았단다.

어느 날, 모든 나무들은 서로 한 번씩 악수를 했지. 악수를 한 두 나무의 번호가 서로소였을 때, 두 나무는 좋은 관계를 형성하고 더 큰 번호의 나무에 오렌지가 하나 자랐어.

악수가 모두 끝난 뒤, 오렌지를 가지지 못한 1번 오렌지 나무에도 오렌지가 하나 자랐단다."

- 1번 오렌지 나무

예를 들어, $N=4$일 경우에는, 1번, 2번 나무는 오렌지를 각각 하나씩 가지고 있고, 3번, 4번 나무는 오렌지를 각각 두 개씩 가지고 있게 된다.

브루는 오렌지 섬의 모든 오렌지를 따 먹으려고 한다. 구체적으로, 브루는 아래와 같은 과정을 통해 오렌지를 먹게 된다.

  1. 아무 나무로 이동해 오렌지를 정확히 하나 따 먹는다.
  2. 그 후, 현재 위치한 나무와 좋은 관계인 나무로 이동해 오렌지를 정확히 하나 따 먹는다.
  3. 오렌지를 모두 먹을 때까지 2번 과정을 반복한다.

브루가 오렌지를 모두 먹을 수 있는지 판별하고, 먹을 수 있는 경우 오렌지를 먹는 순서를 아무거나 하나 출력하는 프로그램을 작성하자.

입력

첫째 줄에는 오렌지 섬에 있는 나무의 수 $N$이 주어진다.

출력

만약 브루가 모든 오렌지를 따 먹는 것이 가능하다면, 브루가 오렌지를 먹는 순서대로 오렌지 나무의 번호를 출력 예시와 같은 형식으로 출력한다.

만약 브루가 모든 오렌지를 따 먹는 것이 불가능하다면, -1을 출력한다.

제한

  • $1 \le N \le 10^3$

서브태스크

번호 배점 제한
1 10

$N \le 7$

2 90

추가 제한 조건이 없다.

예제 입력 1

4

예제 출력 1

1 2 3 4 3 4

출처

Contest > Orange Cup > Orange Cup D번

채점 및 기타 정보

  • 예제는 채점하지 않는다.