시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 56 7 6 37.500%

문제

장기의 말 중 차(車)는 상하좌우 네 방향 중 한 방향으로 몇 칸이든 갈 수 있는 말이다. 예를 들어 차가 아래와 같은 위치에 있다고 할 때, 이 차가 이동할 수 있는 칸은 다음과 같다.

우리는 N×N 모양의 게임판에 N개의 차를 배치하려고 하는데, 다음의 두 가지 조건을 만족시키도록 배치하고 싶다.

1) 어떤 차도 다른 차가 이동할 수 있는 칸에 위치해서는 안 된다. 즉 서로 같은 세로줄 또는 가로줄에 두 개의 차가 위치할 수는 없다.
  2) 두 대각선이 지나는 칸 위에는 차가 위치할 수 없다. N=7인 경우, 대각선이 지나는 칸이란 아래와 같은 칸들을 말한다.

주어진 두 조건을 만족하면서 N×N 모양의 게임판에 N개의 차를 배치하는 프로그램을 작성하시오. 아래는 N=4인 경우 조건을 만족하는 배치가 된다. (색칠된 칸은 차를 놓을 수 없는 칸)

입력

첫째 줄에 N(3≤N≤100,000)이 주어진다.

출력

N개의 줄에 걸쳐, 게임판에서 각 줄의 몇 번째 칸에 차를 배치했는지를 나타내는 칸의 번호를 순서대로 출력한다. 조건을 만족시키는 배치가 둘 이상이면 아무 것이나 출력한다. 배치가 불가능한 경우 첫째 줄에 -1만을 출력한다.

예제 입력

4

예제 출력

3
1
4
2

힌트