Indian National Olympiad in Informatics

Related:

Online Programming Contest, 25-26 March 2006

IARCS home > OLYMPIAD

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