Palíndroms trencats P54747

Statement

thehtml

Dr. Hibbert: Lisa, lo pasarás muy bien aquí. Bueno, ya podemos empezar. Algún palíndromo nuevo?
Jeff Albertson: Ehhem, “someto votemos”.
Dr. Hibbert: Pero el orden es palíndromos, anagramas, comernos la tarta de Lisa y luego votar!
Lisa: Pero es que “someto votemos” es un palíndromo...
Prof. Frink, Jeff Albertson, Lindsey Naegle: Un palíndromo, sí, “someto votemos”. Ohh, pues es verdad!
Seymour Skinner: Lisa, aquí te vas a encontrar entre los tuyos.
Lisa: Aaay, yo entre los míos...

Lamentablement, mentre es menjaven el pastís de la Lisa, el quadern on s’apuntaven tots els palíndroms ha quedat tacat i trencat a trossos. Així doncs, cada paraula ha quedat dividida en diverses parts. Com que en Jeff (el tipus de la imatge de la dreta) ha fracasat miserablement en el seu intent de reconstruir els palíndroms, us demanem que l’ajudeu amb un programa que ho resolgui. Recordeu que un palíndrom és una paraula que es llegeix igual d’esquerra a dreta que de dreta a esquerra.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de trossos n en què s’ha trencat el palíndrom. A continuació vénen els n trossos, formats exclusivament per lletres minúscules. Suposeu 1 ≤ n ≤ 8.

Sortida

Per a cada cas, escriviu el palíndrom que es pot formar amb els diferents trossos. Teniu la garantia que sempre existeix una única resposta.

Public test cases

Input

8
da
ba
learro
zal
azo
rra
ela
bad
3
b
a
a
2
votemos
someto
1
pop

Output

dabalearrozalazorraelabad
aba
sometovotemos
pop

Information

Author: Alex Alvarez
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C++