让我们将网格定义为一组 2 行 13 列的图块。每块瓷砖上都写有一个英文字母。这些字母不必是唯一的:可能有两个或多个图块上写有相同的字母。这是一个网格的示例:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
如果两个图块共享一条边或一个角,我们就说它们是相邻的。在上面的示例网格中,带有字母“A”的图块仅与带有字母“B”、“N”和“O”的图块相邻。瓷砖不与其自身相邻。
如果序列中的每个图块与其后面的图块相邻(序列中的最后一个图块除外,它当然没有后继),则该图块序列称为路径。在此示例中,“ABC”是路径,“KXWIHIJK”也是路径。 “MAB”不是路径,因为“M”与“A”不相邻。一条路径可以多次使用单个图块(尽管该图块不能占据路径中的两个连续位置,因为没有图块与其自身相邻)。
给定一个由 27 个大写英文字母组成的字符串 s。每个英文字母在 s 中至少出现一次。找到一个包含路径的网格,按照路径访问它们的顺序查看该路径的图块,形成字符串 s。如果没有解决方案,请打印“Impossible”(不带引号)。
输入
输入中唯一一行包含字符串 s,由 27 个大写英文字母组成。每个英文字母在 s 中至少出现一次。
输出
输出两行,每行由13个大写英文字符组成,代表网格的行。如果有多个解决方案,请打印其中任何一个。如果没有解决方案,请打印“不可能”。
示例
输入 #1
ABCDEFGHIJKLMNOPQRSGTUVWXYZ
输出 #1
YXWVUTGHIJKLM ZABCDEFSRQPON
输入 #2
BUVTYZFQSNRIWOXXGJLKACPEMDH
输出 #2
Impossible