Hide

Problem J
Three Dice

Given a list of three-letter words, generate one possible set of three, six-sided dice such that each word can be formed by the top faces of some arrangement of the three dice. You must distribute 18 distinct letters across the 18 total faces of the dice. There may be multiple possible sets of dice that satisfy the requirement; any correct set will be accepted.

Input

The first line of input contains an integer $n$ $(1\le n\le 1\, 000)$, which is the number of words.

Each of the next $n$ lines contains one three-letter word made up only of lowercase letters (az). There may be duplicate words in the list, and the words might contain identical letters.

Output

Output a single line. If there exists a set of dice that can form all of the words, output any such set. Output the set of dice as one line with three space-separated strings, each consisting of six lowercase letters. If no such set of dice can be formed, output a single line with the number 0.

Sample Input 1 Sample Output 1
3
lad
fin
sly
zounds plight fakery
Sample Input 2 Sample Output 2
1
dad
0
Sample Input 3 Sample Output 3
11
aft
cog
far
irk
kit
yes
tau
rag
own
uke
via
vortex whacky fusing

Please log in to submit a solution to this problem

Log in