Maximal Orders of Permutations
Memory limit: 64 MB
A permutation of
elements is a one-to-one function (injection)
. An order of permutation
is the minimal
, such that for all
we have:

i.e.
composed with itself
times becomes identity function. For example, the order of the permutation of
elements
is
, because
.
For a given
let us consider permutations of
-elements having the the largest order possible. For example, the maximal order of a permutation of
elements is
. An example of a permutation of
elements whose order is
is
.
Among all permutations of
elements having the maximal order, we would like to find the earliest one (in a lexicographical order). Being more precise, we say a permutation
of
elements is earlier than a permutation
of
elements, if there exists
, such that
for all
and
. The earliest permutation of
elements having an order
is
.
Task
Write a programme that:
- reads from the standard input a set of integers
,
- for each number
(for
) determines the earliest permutation of
elements having the maximal order,
- writes the determined permutations to the standard output.
Input
There is one positive integer
in the first line of the standard input,
. In the following
lines there are positive integers
, one per line,
.
Output
Your programme should write
lines to the standard output. The
'th line should contain a sequence of integers separated by spaces, forming the least permutation of
elements having the maximal order, i.e. the sequence
, where
denotes this permutation.
Example
For the input data:
2
5
14
the correct result is:
2 1 4 5 3
2 3 1 5 6 7 4 9 10 11 12 13 14 8
Task author: Jakub Pawlewicz.