Ant Nest

Interview

Time limit1sMemory limit256 MB

Summary

Given paths of food names from the top floor down, print the merged tree with each node indented by two dashes per depth and children in dictionary order.

Level: Medium6 of 10
Topics: Trie, Tree, String, Sorting
Solved: No attempts yet

Problem

Ants work hard every day, sweating all the way. The world is harsh and nobody knows what comes next, yet the ants are happy today.

The engineer Yunsu wondered why the ants are happy. He decided that the secret lies in the structure of the nest they live in, so he built robot ants.

Each robot ant carries a sensor. It walks down one floor at a time, following rooms that hold food, and when it can go no deeper it stops and sends a signal. The signal lists the food stored in every room the robot passed, from the top floor downward.

Diagram of an ant nest

Yunsu sent in enough robot ants to visit every storage room of the nest. For the nest in the picture above, the robot ants reported this:

KIWI BANANA
KIWI APPLE
APPLE APPLE
APPLE BANANA KIWI

From those reports Yunsu drew the nest by hand:

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

Every floor down adds one more "--" in front of the line, and rooms that branch out of the same room are written in dictionary order of their food names. When two robot ants passed through the same rooms from the top floor down, Yunsu drew that room only once.

Drawing a complicated nest by hand takes too long. Help Yunsu and draw the structure of the nest from the reports of the robot ants.

Input

The first line contains the number of reports $N$ ( $1 \le N \le 1000$ ) sent by the robot ants.

Each of the next $N$ lines contains one report. A line starts with the number of rooms $K$ ( $1 \le K \le 15$ ) that the robot ant passed through, followed by $K$ food names in order from the top floor downward. A food name consists of uppercase letters only, and its length $t$ satisfies $1 \le t \le 15$ .

Output

Print the structure of the nest as a drawing.

Every floor down adds one more "--" in front of the line. A room on the top floor has nothing in front of it, a room one floor below starts with "--", and a room two floors below starts with "----".

When one room branches into several rooms, print the room whose food name comes first in dictionary order first. Among the rooms that branch out of the same room, including the top floor, print each food name only once.

Limits

$1 \le N \le 1000$
$1 \le K \le 15$
$1 \le t \le 15$

Examples3

Example 1

Input

3
2 B A
4 A B C D
2 A C

Expected output

A
--B
----C
------D
--C
B
--A

Example 2

Input

4
2 KIWI BANANA
2 KIWI APPLE
2 APPLE APPLE
3 APPLE BANANA KIWI

Expected output

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

Example 3
Input
```
1
1 A
```
Expected output
```
A
```