Partitioning Items into Non‐Overlapping Collections

You are given a set of N items. Each item is described by an identifier and C characteristics. Your task is to group these items into collections such that each collection contains exactly K items and no two items in the same collection share any characteristic.

If it is impossible to form the required collections under these constraints, output impossible (without quotes).

Details:

• Each item is described by a line consisting of C+1 integers: the first integer is the item identifier, followed by C integers representing its characteristics.
• The items must be partitioned into groups (collections) of size K such that, within each group, the sets of characteristics from different items do not intersect. In other words, for any two items in the same group, the intersection of their characteristic sets must be empty.
• If there is more than one valid partition, output any one of them.

Constraints: You may assume that N is divisible by K and that N is small enough for backtracking solutions to run within time limits.

Example 1:

Input:
5 3 2
1 1 2 3
2 2 3 4
3 1 3 4
4 5 6 7
5 4 5 6
Output:
impossible

</p>

Example 2:

Input:
4 2 2
1 1 2
2 3 4
3 5 6
4 7 8
Output:
1 2
3 4

</p>

inputFormat

The input is read from standard input (stdin) and has the following format:

N C K
item_1
item_2
...
item_N

where:

• N is the number of items.
• C is the number of characteristics each item has.
• K is the number of items that each collection must contain.
• Each of the next N lines describes an item with C+1 space-separated integers: the first integer is the item identifier, and the next C integers are its characteristics.

outputFormat

If it is possible to form a complete partition, output the collections in N/K lines. Each line should contain the K item identifiers (space‐separated) belonging to one collection. If it is impossible to partition the items into collections under the given constraints, output a single line with the string impossible.

## sample

5 3 2
1 1 2 3
2 2 3 4
3 1 3 4
4 5 6 7
5 4 5 6

impossible