Boggle Sort

문제

It is the 25th of February, 2025. You have enjoyed another spirited evening of Boggle with your friends. After everybody left, you have thoroughly cleaned the apartment. All that is left is to bring the Boggle tray in order. You start to wonder: would it be possible to bring the Boggle tray in alphabetic order, without swapping any dice, but only by rotating them?

The Boggle tray consists of $1616$ six-sided dice. Each die is labelled with a letter from the English alphabet on each face. A single die contains a face labelled "Qu". No letter appears $44$ or more times on the same die. By turning a die once, you can move any of the sideways-facing letters up. Turning a die twice moves the downwards-facing letter up.

Figure B.1: Visualization of the first sample input. The $1616$ Boggle dice are shown in reading order. For each die, the face in the center of the cross ("I" in the first die) is upwards-facing and the face on the far right ("Y" in the first die) is downwards-facing. The shaded die faces describe an optimal solution requiring $1515$ turns.

Bring the tray into alphabetically nondecreasing order, using standard reading directions (left-to-right, top-to-bottom), using as few turns as possible. Letter case plays no role and the two-letter face is treated as "Q" followed by "U", so "QuU" is sorted but "QuT" is not.

입력

The input consists of:

• One line with $1616$ letters, describing the currently upwards-facing faces of each die.
• Four lines with $1616$ letters, describing the currently sideways-facing faces of each die.
• One line with $1616$ letters, describing the downwards-facing faces of each die.

In each line, the $ii$th letter describes the $ii$th die for $1\le i\le 161\backslash leq\; i\backslash leq\; 16$. All letters are English uppercase letters (A-Z). The letter "Q" stands for the two-letter face "Qu" and appears exactly once in the input. No letter appears $44$ or more times on the same die.

출력

If it is possible to bring the tops of the dice into alphabetic order, output the minimum number of turns needed to do so. Otherwise, output "impossible".

IAZEEOXSPACKYIGF
APDSSAOHEQAOGGLY
LCERNRFILJINEEWE
BDVLOMRESBATLTRI
TEAAWSINUOOUKVIH
YMNCDHBPTMTDUNUE

15

EXFETDMNMGDBRSRM
TIEGINOVRETACNUA
PRYKASAEATNTSHID
SOHUOEJDHVKYLPLC
UFIYAWBZONUIEIWE
LBELCOQASIOLAEGP

impossible