Indian National Olympiad in Informatics

Online Programming Contest, 5-6 February 2005

IARCS home > OLYMPIAD

Basic Division

Problem 1: Electoral Rolls Revision, (K Narayan Kumar, CMI)

The Chief Electoral Officer of Siruseri has ordered a revision of the electoral rolls. Siruseri is divided into a number of Blocks and an officer is assigned to each block to enumerate the list of voters in the block. Siruseri is a model town and assigns a unique identification number (ID number) to each resident at the time of his birth and he has to quote this in all his dealings with the government. The list compiled by the officer is a listing of the ID numbers of all the voters in his block. This list is in ascending order of ID numbers.

Once he obtains the lists from all the blocks the CEO will combine the lists to get a listing of the ID numbers of all eligible voters in Siruseri. Your task is to help him compile this sorted list from the sorted lists he gets from the different blocks.

Here is an example with four blocks. The listing of the voters in the four blocks is as follows:

349  448  900
 23 1045 1149 9876
785 1002
456  998 1047 9023 9987

Then, the CEO would like to combine these to get the list:

23  349  448  456  785  900  998  1002  1045  1047  1149  9023  9876  9987

Input format

The first line of the input contains a single integer B indicating the number of blocks in Siruseri. The next B lines (lines 2, ..., B+1) contain the voters list from the different blocks. Line i+1 contains the voters list of block i. It consists of a sequence of integers. The first integer indicates the number of voters in Block i. This is followed by i integers, sorted in ascending order, giving the ID numbers of the voters in this block.

Output format

A sequence of integers, one in each line, giving the sorted sequence of ID numbers, in ascending order, of the voters in Siruseri.

Test data

You may assume that B ≤ 500 and that the number of voters in every block is not more than 1000. Further, you may assume that in 50% of the test inputs, B ≤ 60 and each block has at the most 100 voters.

Example

We now illustrate input and output formats using the example described above.

Sample input:

4
3 349 448 900
4 23 1045 1149 9876
2 785 1002
5 456 998 1047 9023 9987

Sample output:

23 
349 
448 
456 
785 
900 
998 
1002 
1045 
1047 
1149 
9023 
9876 
9987



Copyright (c) IARCS 2003-2018;   Last Updated: 01 Mar 2005