Merging Sequences

Time limit1sMemory limit1024 MB

Summary

Given N sequences, output their total length, the sum of distinct values shared by sequences A and B, and the final result of pairwise merging by larger values.

Level: Easy3 of 10
Topics: Implementation, Simulation, Hash map
Solved: No attempts yet

Problem

You are given N sequences of natural numbers. The number of elements in each sequence is known in advance. Solve the following three challenges.

Challenge #1

If all given sequences were written one after another, how many numbers would be written?

Challenge #2

What is the sum of the numbers that appear in both the A-th and the B-th sequence? A number that repeats across the two sequences is added only once.

Challenge #3

Two sequences are merged into one by comparing the values at matching positions (first, second, ...). The larger of the two compared values is placed at that position in the new sequence. If one sequence has no value at a position, the value from the sequence that has that position is used.

Merge the N given sequences in pairs (first with second, third with fourth, ...), and repeat until one sequence remains.

Input

The first line contains a natural number N (1 ≤ N ≤ 128). N is a power of 2.

The second line contains the natural numbers A and B (1 ≤ A < B ≤ N).

Each of the next N lines contains one sequence. The first number M (1 ≤ M ≤ 99) on a line is the number of elements in that sequence, followed by M natural numbers Xi (1 ≤ Xi ≤ 99) on the same line.

Output

The first line contains the natural number that answers Challenge #1.

The second line contains the number that answers Challenge #2.

The third line contains the values of the final merged sequence at its first, second, ..., and last positions.

Hint

Test case 1 explanation: Writing both sequences one after another gives eight numbers. The value 2 appears in both the first and the second sequence. Merging the two sequences gives [6 (24), 5 (5>2), 3, 1].

Test case 2 explanation: Writing all four sequences one after another gives 21 numbers. The numbers that appear in both the third and the fourth sequence are 2, 1, and 3. The sequences are merged as follows:

The first four sequences	First and second, third and fourth merged	Merging the two new sequences
```
6 3 2 4 5
4 7
2 1 3 4 2 7
2 3 2 1 2 3 2 1
```	```
6 7 2 4 5
2 3 3 4 2 7 2 1
```	```
6 7 3 4 5 7 2 1

Examples3

Example 1

Input

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

Expected output

8
2
6 7 5 3 1

Example 2

Input

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

Expected output

21
6
6 7 3 4 5 7 2 1

Example 3

Input

8
4 5
8 1 8 8 9 2 10 6 5
7 4 1 2 1 5 7 10
10 5 3 6 4 6 4 5 3 1 6
1 7
1 10
2 8 7
4 1 4 8 7
9 1 7 2 1 5 9 8 4 3

Expected output

42
0
10 8 8 9 6 10 10 5 3 6