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

CPU Timelimit: | 3 seconds |

Memory limit: | 64M |

Grading style: | ioi |