N quân hậu

Cho một bàn cờ hình vuông kích thước \(N \times N\).

Hãy đặt đúng \(N\) quân hậu lên bàn cờ sao cho không có hai quân hậu nào có thể ăn nhau.

Hai quân hậu được coi là có thể ăn nhau nếu chúng nằm trên cùng một hàng, cùng một cột hoặc cùng một đường chéo.

Yêu cầu. Hãy tìm và in ra một cách đặt \(N\) quân hậu thỏa mãn yêu cầu.

Đề bài đảm bảo luôn tồn tại ít nhất một lời giải.

Input

Dòng duy nhất chứa số nguyên \(N\) \((1 \le N \le 30)\).

Output

In ra một dòng gồm \(N\) số nguyên.

Số thứ \(i\) là cột đặt quân hậu trên hàng thứ \(i\).

Các cột được đánh số từ \(1\) đến \(N\).

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Input

%
4

Output

%
2 4 1 3

Notes

Trong ví dụ, các quân hậu được đặt tại các ô:

Không có hai quân hậu nào nằm trên cùng một cột hoặc cùng một đường chéo.

Scoring

• (30%) \(N \le 10\).
• (30%) \(N \le 15\).
• (40%) Không có ràng buộc bổ sung.