Anatoly Cheng McDougal 在很多方面都是一个典型的学生。只要有可能，他就会尝试剪切和粘贴代码，而不是从头开始编写。不可避免地，这种方法给他带来了麻烦。例如，当他第一次学习树的先序（preorder）、中序（inorder）和后序（postorder）遍历，并得到一段树的先序打印代码（如下左侧所示）时，他只是简单地剪切并粘贴了代码，然后将打印语句移动到正确的位置并重命名了过程。然而，他忘记重命名代码内部的过程调用，导致了如下所示的错误的先序、中序和后序打印代码。
void prePrint(TNode t)
{
output(t.value);
if (t.left != null)
prePrint(t.left);
if (t.right != null)
prePrint(t.right);
}
void inPrint(TNode t)
{
if (t.left != null)
prePrint(t.left);
output(t.value);
if (t.right != null)
prePrint(t.right);
}
void postPrint(TNode t)
{
if (t.left != null)
prePrint(t.left);
if (t.right != null)
prePrint(t.right);
output(t.value);
}此时，Anatoly 的表现不像一个典型的学生。他实际上测试了他的代码！不幸的是，当结果不正确时，他又回到了典型的学生行为。他惊慌失措，开始随机更改所有三个过程中的调用，希望能把事情搞定。不用说，情况比他开始时更糟了。
Anatoly 的教授在一棵随机的字符树上测试了这段代码。当她查看他三个打印程序的输出时，她正确地猜到了发生了什么。然而，她没有直接去看他的代码，而是决定仅通过观察输出来尝试重构 Anatoly 的代码。为了做到这一点，她正确地做出了以下假设：
- 每个打印程序中的输出语句都在正确的位置（例如，在
inPrint程序的两个递归调用之间）。 - 在这三个程序所做的六个递归调用中，恰好有两个调用是
prePrint，恰好有两个是inPrint，恰好有两个是postPrint，尽管可能在错误的程序中。
教授很快意识到，从输出中重构 Anatoly 的代码和测试树并非易事，而且结果可能是模棱两可的。你将不得不帮助她找到所有可能的 Anatoly 代码重构方案。此外，对于每种这样的重构，你需要找到产生观察到的输出的字典序最小的树（如输出部分所述）。
输入格式
输入包含单个测试用例。测试用例由三行上的三个字符串组成：Anatoly 的 prePrint、inPrint 和 postPrint 程序在某棵测试树上的观察输出（按此顺序）。每个字符串由 $n$ 个大写字母组成（$4 \le n \le 26$），且任何字符串中都没有重复的字母。保证测试用例至少有一个解。
输出格式
显示测试用例的所有可能重构，并按最后一段所述的顺序排列。每个重构的输出由两部分组成。第一部分是一行，描述 Anatoly 程序中的六个调用：首先是 Anatoly 的 prePrint 程序中的两个（递归）调用，接着是他 inPrint 程序中的调用，最后是他 postPrint 程序中的调用。这些调用由单词 Pre、In 和 Post 描述，并用空格分隔。例如，如果 Anatoly 的程序是正确的，则重构第一部分的输出结果将是 Pre Pre In In Post Post。
第二部分由三行组成，描述了可能产生观察到的输出的第一棵测试树。第一行是该树正确的先序打印，第二行和第三行分别是正确的中序和后序打印。第一棵树是指先序打印字典序最小的那棵树。如果存在多棵这样的树，则其中第一棵是中序打印字典序最小的那棵。
每个重构都是从 Pre、In 和 Post 中选择的 6 个标记序列。重构的顺序是关于以下标记顺序的字典序：Pre < In < Post。
样例
样例输入 1
HFBIGEDCJA BIGEDCJFAH BIGEDCJFAH
样例输出 1
Pre Post In Post In Pre HFBJCDEGIA BIGEDCJFAH IGEDCJBAFH
样例输入 2
BNLFAGHPEDOCMJIK NLBGAPHCODEIJMKF NLFAGHPEDOCMJIKB
样例输出 2
In Pre In Post Post Pre BLNFKMEHAGPCODIJ NLBAGHPEODCMIJKF NLGAPHDOCEJIMKFB Post Pre In In Post Pre BLNFKICPGAHEODMJ NLBGAPHCODEIJMKF NLAGHPDOECJMIKFB