A sequence of numbers has a well
if it contains three consecutive numbers
such that the endpoints add up more than twice the one in the middle.
Formally, (x_{1}, x_{2}, …, x_{n}) has a well
if it exists at least an i with 2 ≤ i ≤ n − 1
such that x_{i−1} + x_{i+1} > 2 x_{i}.

Write a program that, given an integer n, prints all the sequences with no wells that can be obtained by reordering the sequence (1, 2, …, n).

Input

Input consists of several cases, each one with an n between 1 and 10^{5}.

Output

For every n, print all the permutations with no wells in lexicographical order. Print a line with 10 dashes at the end of every case.

Public test cases

**Input**

2 4 7 1

**Output**

(1,2) (2,1) ---------- (1,2,3,4) (1,3,4,2) (1,4,3,2) (2,3,4,1) (2,4,3,1) (4,3,2,1) ---------- (1,2,3,4,5,6,7) (1,3,4,5,6,7,2) (1,3,5,7,6,4,2) (1,7,6,5,4,3,2) (2,3,4,5,6,7,1) (2,4,6,7,5,3,1) (2,7,6,5,4,3,1) (7,6,5,4,3,2,1) ---------- (1) ----------

Information

- Author
- Albert Oliveras
- Language
- English
- Official solutions
- C++
- User solutions
- C++