레이팅 미적용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 \(16\) 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 \(4\) 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.
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 \(16\) letters, describing the currently upwards-facing faces of each die.
- Four lines with \(16\) letters, describing the currently sideways-facing faces of each die.
- One line with \(16\) letters, describing the downwards-facing faces of each die.
In each line, the \(i\)th letter describes the \(i\)th die for \(1\leq i\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 \(4\) 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