### Indian National Olympiad in Informatics

### Online Programming Contest, 25-26 March 2006

### Basic Division

Problem 1: Next Permutation, *(K Narayan Kumar, CMI)*

It is an interesting exercise to write a program to print out all
permutations of 1, 2, …, *n*. However, since there are
6227020800 permutations of 1, 2, …, 13, it is unlikely that we would
ever run this program on an input of size more than 10.

However, here is another interesting problem whose solution can
also be used to generate permutations. We can order the permutations
of 1, 2, …, *n* under the lexicographic (or dictionary)
order. Here are the permutations of 1,2,3 in lexicographic order:

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

The problem we have is the following: given a permutation of 1,2,
…, *n*, generate the next permutation in lexicographic
order. For example, for `2 3 1 4` the answer is `2 3 4
1`.

Input format

The first line of the input contains two integers, *N* and
*K*. This is followed by *K* lines, each of which
contains one permutation of 1, 2,…,*N*.

Output format

The output should consist of *K* lines. Line *i*
should contain the lexicographically next permutation correponding to
the permutation on line *i*+1 in the input.

Test data

You may assume that 1 ≤ *N* ≤ 1000 and *K* ≤
10.

Example

We now illustrate the input and output formats using the example
described above.

Sample input

3 2
3 1 2
2 3 1

Sample output

3 2 1
3 1 2