Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Russian Dolls
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1313 Accepted: 331 Special Judge

Description

Russian nesting dolls are brightly painted hollow wooden figures. The dolls in a set have roughly the same shape, typically humanoid, but different sizes. When the set is assembled, the biggest doll contains the second-biggest doll, the second-biggest contains the third-biggest, and so on.
We can approximate the shape of a doll as a cylinder of height h, diameter d, and wall thickness w. Such a doll would have a hollow of height h-2w and diameter d-2w.

Boris and Natasha each has a set of dolls. The sets are nearly identical; each has the same number of dolls, which look the same but differ in their dimensions. Last night Boris and Natasha were playing with their dolls and left them in the living room. Their mother tidied them away, dumping them all in one box. Can you help Boris and Natasha separate their sets of dolls?

Input

Standard Input will consist of several test cases. The first line of each test case will contain n, the number of dolls in each set (1 < n <= 100). 2n lines follow; each gives the dimensions, h, d, w of a different doll (h,d >= 2w > 0). A line containing 0 follows the last test case.

Output

For each test case, separate the dolls into two sets of nesting dolls such that, within each set, the dolls fit within each other, standing straight up, as described above. The first n lines of output should give the dimensions of the dolls in one set, in decreasing order by height. The next line should contain a single hyphen, "-". The next n lines should give the dimensions of the dolls in the second set, also in decreasing order by height. There will always be a solution. If there are many solutions, any will do. Output an empty line between test cases.

Sample Input

```3
100 100 3
97 97 3
94 94 3
91 91 3
88 88 3
85 85 3
5
100 100 1
97 97 3
98 98 1
96 96 1
94 94 1
92 92 1
90 90 1
88 88 1
86 86 1
84 84 1
0
```

Sample Output

```100 100 3
94 94 3
88 88 3
-
97 97 3
91 91 3
85 85 3

100 100 1
98 98 1
96 96 1
94 94 1
92 92 1
-
97 97 3
90 90 1
88 88 1
86 86 1
84 84 1
```

Source

[Submit]   [Go Back]   [Status]   [Discuss]