Hoán vị 2

Cho số nguyên \(n\). Hãy in ra tất cả các hoán vị của dãy số \(1, 2, \ldots, n\) sao cho không có hai phần tử nào đứng cạnh nhau có hiệu bằng \(1\) (tức là nếu \(a_i\) và \(a_{i+1}\) là hai phần tử kề nhau trong hoán vị, thì \(|a_i - a_{i+1}| \ne 1\)).

Các hoán vị cần được in ra theo thứ tự từ điển tăng dần.

Input

Một dòng duy nhất chứa số nguyên \(n\) \((4 \le n \le 8)\).

Output

In ra tất cả các hoán vị thỏa mãn yêu cầu, mỗi hoán vị trên một dòng, các số cách nhau bởi một dấu cách.

Nếu không tồn tại hoán vị nào thỏa mãn, không in gì cả.

Sample Input 1

4

Sample Output 1

2 4 1 3
3 1 4 2