Background

The score for this problem follows the original COCI setting, with a full score of $80$.

Problem Description

Do you like playing crossword puzzles? If so, you may know the traditional beginner puzzle shown below:

• Horizontally:

  1. A device used to cool a computer

  2. Solid water

  3. Used to obtain

• Vertically:

  1. A small, soft, sweet fruit

  2. A powerful playing card

  3. A fisherman's tool

Given six three-letter words, you need to place them into a $3 \times 3$ grid so that these words all appear both horizontally and vertically.

Input Format

The input consists of $6$ lines, each containing a three-letter word in uppercase letters. They are guaranteed to be given in lexicographical order.

Output Format

If no solution exists, output $0$. Otherwise, output a $3 \times 3$ matrix of letters in three lines.

If multiple solutions exist, output the solution with the smallest lexicographical order of the nine characters formed by concatenating each row end-to-end.

ANA
ANA
DAR
DAR
RAD
RAD

DAR
ANA
RAD

EVO
HEP
HIR
IVA
PAD
ROD

HEP
IVA
ROD

AKO
CES
DOC
DON
ESI
KES

0

Hint

Translated by ChatGPT 5