President has declared the development of tram service a priority national
project. As a part of this project, Yekaterinburg will receive enough budget
funds to carry out a complete reconstruction of the city's tram network.
There are 2n tram stops in Yekaterinburg. In the course of
reconstruction, the stops will be left in their places and no new stops will be
built, but new tram railways will be laid so that it will be possible to go by
tram from every tram stop to any other tram stop without any intermediate
Having studied messages at the tram forum, the city authorities found out
that citizens would be satisfied with the reconstruction only if for every pair
of tram stops there would be a tram route connecting these stops without any
intermediate stops. It is clear that the network of
n(2n − 1) routes consisting of only two stops
each satisfies this requirement. However, Yekaterinburg Mayor wants exactly
n routes to be left after the reconstruction, and each tram must make
exactly 2n stops (including the final ones) on its route. Trams must go
along these routes in both directions. Suggest a plan of reconstruction that
will satisfy both citizens and Mayor.
The only input line contains the integer n,
1 ≤ n ≤ 100.
Output n lines describing tram routes. Each route
is a sequence of integers in the range from 1 to 2n separated by a
space. A route may go through a stop several times. If the problem has several
solutions, you may output any of them. If there is no solution, output one line
containing the number −1.
1 6 2 1 3 4
2 3 6 5 4 6
5 1 4 2 5 3
Problem Author: Alexander Ipatov (idea — Magaz Asanov)
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008