Polish version    English version  
  History of OI -> XI OI 2003/2004 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Rules
For contestants
Helpful resources
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
XI Olympiad in Informatics 2003/2004

Task: MAK

Maximal orders of permutations

III stage competition (national finals)  
Source file: mak.*
Memory limit: 64 MB

A permutation of n elements is a one-to-one function (injection) p: {1,2,...,n} -> {1,2,...,n}. An order of permutation p is the minimal k >= 1, such that for all i=1,2,...,n we have:

, i.e. p composed with itself k times becomes identity function. For example, the order of the permutation of 3 elements p(1)=3, p(2)=2, p(3)=1 is 2, because p(p(1))=1, p(p(2))=2, p(p(3))=3.

For a given n let us consider permutations of n-elements having the the largest order possible. For example, the maximal order of a permutation of 5 elements is 6. An example of a permutation of 5 elements whose order is 6 is p(1)=4, p(2)=5, p(3)=2, p(4)=1, p(5)=3.
Among all permutations of n elements having the maximal order, we would like to find the earliest one (in a lexycographic order). Being more precise, we say a permutation p of n elements is earlier than a permutation r of n elements, if there is i, such that p(j) = r(j) for all j < i and p(i) < r(i). The earliest permutation of 5 elements having an order 6 is p(1)=2,p(2)=1,p(3)=4,p(4)=5,p(5)=3.

Task

Write a programme that:

  • reads from the standard input a set of integers n1,n2,...,nd,
  • for each number ni (for i=1,2,...,d) determines the earliest permutation of ni elements havaing the maximal order,
  • writes the determined permutations to the standard output.

Input

There is one positive integer d in the first line of the standard input, 1 <= d <= 10. In the following d lines there are positive integers n1, n2, ..., nd, one per line, 1 <= ni <= 10.000.

Output

Your programme should write d lines to the standard output. The ith line should contain a sequence of integers separated by spaces, forming the least permutation of ni elements having the maximal order, i.e. the sequence p(1), p(2), ..., p(ni), where p denotes this permutation.

Example

For the following input data:
2
5
14
the correct answer is:
2 1 4 5 3
2 3 1 5 6 7 4 9 10 11 12 13 14 8



Print friendly version