Annealing peaceful queens!

Arrange N queens on a square N×N board, so that no two hit each other - a very difficult task. That's why it instructed you.

Input

In a single input line is the number 4 ≤ N ≤ 200 - size board.

Output

Output of N numbers a: a_i - is the number of horizontal, on which you put the queen occupying the i-thuja vertical. Numbering of contours comes from the bottom up, from 1 to N (as in conventional chess board).

Examples