\(n \times n\) 체스판에 퀸 \(n\)개를 놓으려고 한다.

어떤 두 퀸도 서로 공격할 수 없도록 놓아야 한다.

퀸은 같은 행, 같은 열, 같은 대각선에 있는 칸을 공격할 수 있다.

가능한 배치가 여러 개라면, 열 번호 수열이 사전순으로 가장 작은 배치를 출력하시오.

열 번호 수열

각 행에는 퀸이 정확히 하나씩 놓인다.

\(i\)번째 행에 놓인 퀸의 열 번호를 \(a_i\)라고 하자.

이때 \(a_1, a_2, \ldots, a_n\)을 이 배치의 열 번호 수열이라고 한다.

두 수열을 비교할 때는 앞에서부터 차례대로 비교한다. 처음으로 값이 다른 위치에서 더 작은 값을 가진 수열이 사전순으로 더 작다.

입력

첫째 줄에 체스판의 크기 \(n\)이 주어진다.

출력

사전순으로 가장 작은 열 번호 수열을 공백으로 구분하여 출력한다.

제한 사항

• \(4 \le n \le 12\)

예제 입력 1

4

예제 출력 1

2 4 1 3

예제 설명 1

\(n = 4\)일 때 가능한 열 번호 수열은 다음 두 가지이다.

2 4 1 3
3 1 4 2

이 중 사전순으로 가장 작은 수열은 2 4 1 3이다.

2 4 1 3은 다음 배치를 의미한다.

.Q..
...Q
Q...
..Q.

Q는 퀸이 놓인 칸, .은 빈 칸을 의미한다.