High School Programming League Problems Archive

You are given N sets of positive integers. You are to write a program that finds a sequence of integers S such that:

• Each set appears as the set of elements of some (at least one) sub-word of S.
• The length of S must be as small as possible.
• Each number in the sequence must belong to at least one of the sets.

Input

Input starts with an integer (1 <= N <= 500), the number of sets. N lines follow, each describing a set in the following manner: an integer (1 <= L <= 100), representing the size of the set and L space separated integers. Sets will be composed of integers from the closed interval [0, 99].

Output

In the first line of output, print the sequence S in the same manner of the sets. The second line of output must consist of N space separated integers, with the i-th integer being the zero-indexed initial position of a subword containing the i-th set.

Scoring

You will get max(0, SOL-M) points for a single test, where SOL is the sum of lengths of all sets and M is the length of the printed sequence.

The number of points displayed in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Example

Input:
4
10 4 7 5 1 8 9 2 0 6 3
7 5 9 1 6 3 4 0
4 4 5 3 8
8 3 9 0 7 6 8 4 2

Output:
16 9 0 4 1 3 5 6 7 9 0 8 2 3 4 8 5
2 0 12 6

Scoring:
13

Notes

• For the first three weeks of the series (till noon Saturday, November 21) all submissions to this problem will be visible to all users and tested on 5 data sets only.
• For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on all 10 data sets. (Earlier solutions will also be extended to all 10 data sets.)