Tournament P26606

Consider an all-play-all tournament, in which each team (or player) will meet every other participant exactly once, in turns. For instance, if we have n = 2m football teams, we will have m concurrent matches in n − 1 different days. In the end, we aim for each team to have competed against all the other teams. Additionally, for fairness, we want every team to play m times at home and m−1 times away, or m−1 times at home and m times away. A similar situation would arise in a chess tournament, where we require all the players to have as many white pieces as black pieces (plus minus one).

Given the n names of the teams (or players), can you schedule all the matches?

Input

Input consists of several cases, each with n, followed by n different names made up of only lowercase letters. Assume 2 ≤ n ≤ 1000, and that n is even.

Output

Print n lines for each case. The first n−1 lines should have m matches separated by spaces. A match is a pair of names separated by a dash, where the first team plays at home and the second team plays away. End each case with a line with 10 asterisks. Since there is more than one solution, print any one. Follow strictly the format of the sample output.