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 |