Generisati sve permutacije brojeva od 1 do n koje ne sadrže dva uzastopna parna broja.

Ulaz

Sa standardnog ulaza se učitava ceo broj n (1 ≤ n ≤ 9).

Izlaz

Na standardni izlaz ispisati sve permutacije brojeva od 1 do n koje ne sadrže dva uzastopna parna broja, svaku u zasebnom redu. Elementi permutacije se ispisuju razdvojeni razmakom.

Primer

Ulaz

4

Izlaz

1 2 3 4
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
3 2 1 4
3 4 1 2
4 1 2 3
4 1 3 2
4 3 1 2
4 3 2 1