No wells P44291

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, \dots, x_n)$ has a well if it exists at least an $i$ with $2 \le i \le 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, \dots, 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.