BPC 1 J5 - Set

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Python 2.0s
Memory limit: 256M

Author:
Problem type

You are playing with some cards. Each card has N symbols on it. There are K different possible symbols, so we will represent each card as a sequence of N integers, each between 1 and K (inclusive). You have a deck of K^N cards, where every combination of symbols appears on exactly one card. You are playing a game where you try to arrange the cards into sets. A set of cards consists of K cards, such that across these cards, all K symbols appear in each of the N positions exactly once. Your goal is to split the deck into sets such that each card is in exactly one set. Your friend has already started playing and has already made one valid set. Write a program to arrange the remaining K^N - K cards into valid, non-overlapping sets.

Constraints

2 \le N, K

K^N \le 500\,000

The initial set is guaranteed to be valid.

Input Specification

The first line contains two integers, N and K.

The next K lines contain N integers each, representing the cards your friend already picked.

Output Specification

You should output descriptions of the K^{N-1} - 1 sets you will make.

The description of each set should have K lines containing N integers each, representing the cards in that particular set.

You may output any valid way of partitioning the remaining cards into valid sets, and you may output the cards in a specific set in any order.

Sample Input

2 3
1 3
2 2
3 1

Sample Output

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

Explanation for Sample

The three sets are

1 3
2 2
3 1

(which was given in the input),

3 2
1 1
2 3

and

3 3
2 1
1 2

Note how all 9 cards each appeared exactly once.


Comments

There are no comments at the moment.