Anatoly Cheng McDougal ist in vielerlei Hinsicht ein typischer Student. Wann immer möglich, kopiert er Code und fügt ihn ein, statt ihn von Grund auf neu zu schreiben. Unweigerlich führt das zu Problemen. Als er beispielsweise erstmals die Preorder-, Inorder- und Postorder-Traversierung von Bäumen kennenlernte und Code für die Preorder-Ausgabe eines Baums erhielt (unten links gezeigt), kopierte er diesen einfach, verschob die Ausgabeanweisung an die richtige Stelle und benannte die Prozedur um. Allerdings vergaß er, die Prozeduraufrufe innerhalb des Codes umzubenennen, wodurch der unten gezeigte fehlerhafte Code für Inorder- und Postorder-Ausgaben entstand.

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);
}

An diesem Punkt verhielt sich Anatoly nicht wie ein typischer Student: Er testete seinen Code tatsächlich! Als die Ergebnisse falsch waren, fiel er leider wieder in typisches Studentenverhalten zurück. Er geriet in Panik und begann, die Aufrufe in allen drei Prozeduren zufällig zu ändern, in der Hoffnung, sie richtig hinzubekommen. Natürlich wurde die Lage dadurch noch schlimmer als zu Beginn.

Anatolys Professorin testete den Code an einem zufälligen Baum aus Zeichen. Beim Betrachten der Ausgaben seiner drei Ausgabeprozeduren erriet sie richtig, was geschehen war. Statt jedoch direkt den Code anzusehen, wollte sie versuchen, Anatolys Code allein anhand der Ausgaben zu rekonstruieren. Dazu traf sie folgende zutreffende Annahmen:

1. Die Ausgabeanweisung jeder Ausgabeprozedur steht an der richtigen Stelle (beispielsweise zwischen den beiden rekursiven Aufrufen in inPrint).

2. Von den sechs rekursiven Aufrufen in den drei Prozeduren rufen genau zwei prePrint, genau zwei inPrint und genau zwei postPrint auf, allerdings möglicherweise innerhalb der falschen Prozeduren.

Bald erkannte die Professorin, dass es keine einfache Aufgabe war, Anatolys Code und den Testbaum aus den Ausgaben zu rekonstruieren, und dass das Ergebnis mehrdeutig sein konnte. Du sollst ihr helfen, alle möglichen Rekonstruktionen von Anatolys Code zu finden. Außerdem sollst du für jede Rekonstruktion den alphabetisch ersten Baum bestimmen, der die beobachteten Ausgaben erzeugt, wie im Ausgabeabschnitt beschrieben.

Eingabe

Die Eingabe enthält einen einzelnen Testfall. Dieser besteht aus drei Zeichenketten in drei getrennten Zeilen: den beobachteten Ausgaben von Anatolys Prozeduren prePrint, inPrint und postPrint (in dieser Reihenfolge) für einen Testbaum. Jede Zeichenkette besteht aus $n$ Großbuchstaben ($4 \le n \le 26$), wobei sich innerhalb keiner Zeichenkette Buchstaben wiederholen. Es ist garantiert, dass mindestens eine Lösung existiert.

Ausgabe

Gib alle möglichen Rekonstruktionen für den Testfall in der im letzten Absatz unten beschriebenen Reihenfolge aus. Die Ausgabe jeder Rekonstruktion besteht aus zwei Teilen. Der erste Teil ist eine einzelne Zeile und beschreibt die sechs Aufrufe in Anatolys Prozeduren: zuerst die beiden (rekursiven) Aufrufe in prePrint, dann die Aufrufe in inPrint und zuletzt diejenigen in postPrint. Die Aufrufe werden durch die Wörter Pre, In und Post beschrieben, durch Leerzeichen getrennt. Wären Anatolys Prozeduren beispielsweise korrekt, lautete der erste Teil der Rekonstruktion Pre Pre In In Post Post.

Der zweite Teil besteht aus drei Zeilen und beschreibt den ersten Testbaum, der die beobachteten Ausgaben erzeugt haben könnte. Die erste Zeile ist die korrekte Preorder-Ausgabe des Baums; die zweite und dritte Zeile enthalten die korrekten Inorder- beziehungsweise Postorder-Ausgaben. Der erste Baum ist derjenige mit der alphabetisch ersten Preorder-Ausgabe. Gibt es mehrere solche Bäume, wird darunter derjenige mit der alphabetisch ersten Inorder-Ausgabe gewählt.

Jede Rekonstruktion ist eine Folge von 6 Tokens aus Pre, In und Post. Die Rekonstruktionen werden lexikographisch nach folgender Tokenreihenfolge geordnet: $\texttt{Pre} < \texttt{In} < \texttt{Post}$.

Beispiele

Eingabe 1

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Ausgabe 1

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Eingabe 2

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

Ausgabe 2

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB