Anatoly Cheng McDougal は多くの点で典型的な学生です。可能な限り、最初からコードを書く代わりにコピーして貼り付けようとします。当然、この方法は問題を引き起こします。例えば、木の行きがけ順、通りがけ順、帰りがけ順の走査を初めて学び、木を行きがけ順に出力するコード（下の左側）を渡されたとき、彼は単にコードをコピーして貼り付け、出力文を正しい位置に移動して手続きの名前を変更しました。しかし、コード内部の手続き呼び出しの名前を変更し忘れたため、下に示す誤った通りがけ順と帰りがけ順の出力コードになりました。
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 は典型的な学生らしくない行動をしました。なんとコードをテストしたのです！残念ながら、結果が正しくないと、また典型的な学生の行動に戻りました。彼は慌てて、正しくなることを願いながら、3 つすべての手続き内の呼び出しをでたらめに変更し始めました。言うまでもなく、状況は最初よりさらに悪くなりました。
Anatoly の教授は、文字からなるランダムな木でコードをテストしました。3 つの出力手続きの出力を見て、何が起きたかを正しく推測しました。しかし、直接コードを見る代わりに、出力を観察するだけで Anatoly のコードを復元してみることにしました。そのために、次の正しい仮定を置きました。
各出力手続きの出力文は正しい位置にある（例えば
inPrint手続きでは 2 回の再帰呼び出しの間にある）。3 つの手続きにある 6 回の再帰呼び出しのうち、ちょうど 2 回が
prePrint、ちょうど 2 回がinPrint、ちょうど 2 回がpostPrintへの呼び出しである。ただし、誤った手続き内に置かれている可能性がある。
教授はすぐに、出力から Anatoly のコードとテスト用の木を復元するのは簡単ではなく、結果も一意とは限らないと気付きました。あなたは彼女を助け、Anatoly のコードの可能な復元をすべて求めなければなりません。さらに、各復元について、観察された出力を生成する、アルファベット順で最初の木（出力の節で説明）を求めてください。
入力
入力は 1 つのテストケースからなります。テストケースは別々の 3 行に書かれた 3 つの文字列からなり、あるテスト用の木に対する Anatoly の prePrint、inPrint、postPrint 手続きの観察された出力を、この順に表します。各文字列は $n$ 個の英大文字からなり（$4 \le n \le 26$）、どの文字列内にも同じ文字は 2 回現れません。少なくとも 1 つの解が存在することが保証されます。
出力
このテストケースに対する可能な復元をすべて、以下の最後の段落で説明する順序で出力してください。各復元の出力は 2 つの部分からなります。最初の部分は 1 行で、Anatoly の手続き内の 6 回の呼び出しを表します。まず prePrint 手続き内の 2 回の（再帰）呼び出し、次に inPrint 手続き内の呼び出し、最後に postPrint 手続き内の呼び出しを並べます。呼び出しは単語 Pre、In、Post で表し、空白で区切ります。例えば、Anatoly の手続きが正しければ、復元の最初の部分の出力は Pre Pre In In Post Post となります。
2 番目の部分は 3 行で、観察された出力を生成できる最初のテスト用の木を表します。最初の行は木の正しい行きがけ順の出力、2 行目と 3 行目はそれぞれ正しい通りがけ順と帰りがけ順の出力です。最初の木とは、行きがけ順の出力がアルファベット順で最初の木です。そのような木が複数ある場合は、その中で通りがけ順の出力がアルファベット順で最初の木を選びます。
各復元は Pre、In、Post から選んだ 6 個のトークンの列です。復元は、トークンの順序を $\texttt{Pre} < \texttt{In} < \texttt{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