Problem D
Úllen Dúllen Doff 2

Photo from flickr.com

Lárus is a middle manager at a stellar company, He manages $n$ members of the staff, all of which are related to him except for one.

When a new assignment pops up, Lárus is in charge of assigning it to a member of the staff. Lárus wants to minimise the work his relatives must do. However, he cannot simply pick the same person every time.

To ensure people do not believe Lárus is practising nepotism, He lines the people up in a circle and uses a mantra to pick a person at random for the assignment. First he picks a staff member at which to point and recites the first word. He then recites the rest of the mantra and points to the next staff member to the right for each word that he recites.

The mantra is as follows:

Úllen dúllen doff kikke lane koff koffe lane bikke bane úllen dúllen doff.

How can Lárus line up the staff members so that his relatives do not get the assignment?

Input

The first line of input contains one integer $n$, the number of staff members. Then $n$ lines follow, where each line contains one name. The first name is the staff member which is not related to Lárus.

You may assume that each name is unique and consists of $1$ to $10$ lowercase English letters.

Output

Output $n$ lines, where each line contains one name of a staff member and such that no name is repeated. Lárus will use the ordering you output to recite the mantra and pick the staff member receiving the assignment. If the ordering you output results in one of his relatives being picked, then your solution will be considered wrong.

Scoring

The number of staff members, $n$, can range from $1$ to $20$. There exists a test group for each possible value of $n$ and each group is worth $5$ points. You must solve all the test cases in a test group to earn the points for that group.

Explanation of samples

In the first sample, one possible solution is to iterate through the same order as the input, resulting in the following steps:

• Úllen: Arnar

• dúllen: Atli

• doff: Bjarni

• kikke: Bjarki

• lane: Hannes

• koff: Unnar

• koffe: Arnar

• lane: Atli

• bikke: Bjarni

• bane: Bjarki

• úllen: Hannes

• dúllen: Unnar

• doff: Arnar

Since Arnar ends up being the final choice, the output is considered correct.

In the second sample, one possible answer is to iterate through the following order:

• Úllen: v

• dúllen: x

• doff: y

• kikke: a

• lane: b

• koff: c

• koffe: p

• lane: q

• bikke: r

• bane: s

• úllen: t

• dúllen: u

• doff: z

In the end, z is chosen and the output is considered correct.

Note that many other correct outputs exist and that in the second sample we do not reach the final two values in the order given.

6
arnar
atli
bjarni
bjarki
hannes
unnar

arnar
atli
bjarni
bjarki
hannes
unnar

15
z
x
y
a
b
c
p
q
r
s
t
u
v
w
o

v
x
y
a
b
c
p
q
r
s
t
u
z
w
o