Hyperloop

In August 2013 a design appeared for a new means of transport called Hyperloop, in which capsules travel through a tube at a thousand kilometres per hour. One thing nobody knows yet: the first line will not connect two big cities, it will connect two small provincial towns. Following that example, every two of the country's $N$ cities will be joined directly by one two-way Hyperloop tube.

Once the tubes open, you have to organize several sightseeing routes. One route visits all $N$ cities, each exactly once, and returns to the city it started from, so it uses exactly $N$ tubes. To keep the traffic down, two different routes may not share a tube, no matter which way they run through it.

Because $N$ is odd, you can organize $(N-1)/2$ routes and leave no tube unused. Construct those routes.

The first line contains the number of cities $N$. $N$ is odd and $3 \le N < 2000$. The cities are numbered from 1 to $N$.

Print $(N-1)/2$ routes, one per line. On each line print the $N$ city numbers the route visits, in order from the starting city, separated by single spaces. Do not repeat the starting city at the end.

Many sets of routes satisfy the conditions, so only the one built by the following rule is accepted.

Let $M = (N-1)/2$. Put city 1 in the centre and place the other $N-1$ cities around a circle. The seats are numbered $0$ to $N-2$, and seat $p$ holds city $p+2$.

For $k = 0, 1, \dots, M-1$, route $k$ starts at city 1, visits the cities in seats $c_0, c_1, \dots, c_{N-2}$ in that order, and returns to city 1, where

$c_i = \begin{cases} k - i/2 & (i \text{ even}) \\ k + (i+1)/2 & (i \text{ odd}) \end{cases}$

and every seat number is taken modulo $N-1$. In other words the seats run $k,\; k+1,\; k-1,\; k+2,\; k-2,\; \dots,\; k+(M-1),\; k-(M-1),\; k+M$ stepping alternately forward and backward with a growing gap, which covers all $N-1$ seats. Print the routes in increasing order of $k$.