Tower of Tablets

After digging around in The Temple of the Sun, you've come across some ancient tablets you're sure are worth a fortune! Each one contains two glyphs, that look oddly similar to English letters.

Unfortunately, the tablets contain an ancient curse dictating how they can be stacked in your bag:

• Tablets on the top/bottom of the stack must have one glyph with the same type and position on 1 tablet above/below.

• Tablets in the middle of the stack must have two glyphs with the same type and position on at least 1 tablet above and 1 tablet below.

For example, given the tablets [AB], [AD], [CA], [AA], [CB], you could stack them in the order:

• [AB]
• [CB]
• [CA]
• [AA]
• [AD]

Is it possible to pack all the tablets in your bag without them exploding? If so, how will you stack them?

Input

The first line consists of an integer ~N~ ~(1 \leq N \leq 10^5)~, the number tablets you've found.

The second lines contains the ~N~ strings, representing the glyphs found on each tablet. These glyphs are uppercase english letters, and there may are exactly 2 on each tablet.

Note: The glyphs on tablets can be duplicated. For example, AB could appear twice.

Output

Output the glyphs of the tablets in the order they can be stacked, such that they doesn't explode.

If it's impossible to stack the tablets without them exploding, output -1.

Note: There can be many valid orderings of tablets. If multiple orderings exist, output any of them.

Example

Input

4
AB
AD
AB
CB

Output

AD
AB
AB
CB

This is one valid stack of the tablets.

Example

Input

2
AB
BA

Output

-1

While the two tablets contain the same glyphs, they aren't in the same position, so they can't be matched up.

Example

Input

3
AB
AC
AD

Output

-1

It's not possible to place any tablet in the middle of the stack, and have both its glyphs match another above/below it.

Example

Input

4
AA
AA
BB
BB

Output

-1

AA and BB will never have share least one matching glyph, so it's not possible to create a stack that satisfies the conditions.

Example

Input

4
AB
CD
CB
ED

Output

ED
CD
CB
AB

This is one valid stack of the tablets.