Concatenated words X67572

Statement

Given $n$ words, print all the ways to concatenate them so that there are no two equal adjacent letters.

Input

Input consists of an $n$ between 1 and 8, followed by $n$ words, each one made up of between 1 and 10 lowercase letters. No word has two adjacent equal letters.

Output

Print all the correct ways to concatenate the $n$ words, one per line.

Information about the checker

You can print the solutions to this exercise in any order.

Public test cases

Input

2
z
abcdz

Output

zabcdz

Input

3
adefghijka
b
cxyzc

Output

adefghijkabcxyzc
adefghijkacxyzcb
badefghijkacxyzc
bcxyzcadefghijka
cxyzcadefghijkab
cxyzcbadefghijka

Input

2
ie
ei

Output

Input

3
a
b
b

Output

bab
bab

Information

Author
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++ Python