Ships

Time limit1sMemory limit512 MB

Summary

Parse a run-length encoded N×N board, find connected ship squares (edge adjacency), and report each ship's tonnage with counts in decreasing tonnage order.

Level: Medium7 of 10
Topics: Implementation, Union-find, Simulation, Array
Solved: No attempts yet

Problem

The board of the "Ships" game consists of N×N squares. Each square may belong to some ship or be empty. If two squares belong to ships and have a common edge, then both squares belong to the same ship. Squares of different ships have no common points. The tonnage of a ship is the number of squares belonging to that ship.

In the given example the squares belonging to ships are marked black, and the board contains one 29-ton ship, three 7-ton ships, two 4-ton ships and three one-ton ships.

Write a program that, for a given description of a game board, calculates the number of ships and the tonnage of each ship.

Input

The first line of input contains one positive integer N (N < 30000).

Each of the next N lines gives information about one board row, describing groups of squares belonging to ships from left to right in one of two formats:

<number_of_square_column>, if the square in the given column belongs to a ship, but the squares to the left and to the right are free;
<number_of_first_square_column>-<number_of_last_square_column>, if all consecutive squares from the first to the last (inclusive) belong to a ship and the squares to the left and to the right of this group are free.

Square groups are separated by commas, and each line ends with a semicolon. There are no spaces in the lines. If a board row has no ship squares, the corresponding line contains only one semicolon. The total number of ships does not exceed 1000, and the tonnage of any ship does not exceed 1000 tons.

Output

Output information about the ships. Each line must contain exactly two integers separated by a space. The first number is the tonnage, and the second is the number of ships having that tonnage. Tonnages must be given in decreasing order, and a tonnage is output only if there is at least one ship having that tonnage.

Examples1

Example 1

Input

12
2-4,7,9;
1,4,11-12;
1,4,10,12;
1,4-8,10-12;
1,8;
1,3-6,8,10-12;
1,3,5-6,8,11;
1,8,10-12;
1-8;
;
2;
2-4,7-10,12;

Expected output