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.