Anatoly Cheng McDougal jest pod wieloma względami typowym studentem. Kiedy tylko może, woli kopiować i wklejać kod niż pisać go od zera. Nieuchronnie prowadzi to do problemów. Na przykład, kiedy poznał przejścia drzewa w porządku preorder, inorder i postorder oraz otrzymał kod wypisujący drzewo w porządku preorder (poniżej po lewej), po prostu skopiował i wkleił kod, przesunął instrukcję wypisania na właściwe miejsce i zmienił nazwę procedury. Zapomniał jednak zmienić nazwy wywołań procedur wewnątrz kodu, co dało pokazany poniżej błędny kod wypisywania inorder i 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);
}

W tym momencie Anatoly zachował się nietypowo jak na studenta: rzeczywiście przetestował swój kod! Niestety, gdy wyniki okazały się niepoprawne, wrócił do typowego zachowania. Spanikował i zaczął losowo zmieniać wywołania we wszystkich trzech procedurach, licząc, że w ten sposób naprawi kod. Nie trzeba dodawać, że sytuacja stała się jeszcze gorsza niż na początku.

Prowadząca Anatoly’ego przetestowała kod na losowym drzewie znaków. Patrząc na wyniki trzech procedur wypisujących, poprawnie odgadła, co się stało. Zamiast jednak od razu zajrzeć do kodu, postanowiła spróbować odtworzyć kod Anatoly’ego wyłącznie na podstawie wyników. W tym celu przyjęła następujące poprawne założenia:

1. Instrukcja wypisania w każdej procedurze znajduje się we właściwym miejscu (na przykład pomiędzy dwoma wywołaniami rekurencyjnymi w procedurze inPrint).

2. Spośród sześciu wywołań rekurencyjnych w trzech procedurach dokładnie dwa wywołują prePrint, dokładnie dwa inPrint i dokładnie dwa postPrint, choć mogą znajdować się w niewłaściwych procedurach.

Wkrótce prowadząca zrozumiała, że odtworzenie kodu Anatoly’ego i drzewa testowego z wyników nie jest proste i może być niejednoznaczne. Musisz pomóc jej znaleźć wszystkie możliwe odtworzenia kodu Anatoly’ego. Ponadto dla każdego z nich należy znaleźć pierwsze alfabetycznie drzewo (zgodnie z opisem w sekcji wyjścia), które daje zaobserwowane wyniki.

Wejście

Wejście zawiera jeden przypadek testowy. Składa się on z trzech napisów w trzech osobnych wierszach: zaobserwowanych wyników procedur prePrint, inPrint i postPrint Anatoly’ego (w tej kolejności) na pewnym drzewie testowym. Każdy napis zawiera $n$ wielkich liter ($4 \le n \le 26$), bez powtórzeń wewnątrz któregokolwiek napisu. Gwarantowane jest istnienie co najmniej jednego rozwiązania.

Wyjście

Wypisz wszystkie możliwe odtworzenia dla przypadku testowego, w kolejności opisanej w ostatnim akapicie poniżej. Wynik dla każdego odtworzenia składa się z dwóch części. Pierwsza to jeden wiersz opisujący sześć wywołań w procedurach Anatoly’ego: najpierw dwa wywołania (rekurencyjne) w prePrint, następnie wywołania w inPrint, a na końcu w postPrint. Wywołania opisuje się słowami Pre, In i Post, oddzielonymi spacjami. Na przykład, gdyby procedury Anatoly’ego były poprawne, pierwsza część odtworzenia miałaby postać Pre Pre In In Post Post.

Druga część składa się z trzech wierszy i opisuje pierwsze drzewo testowe, które mogło dać zaobserwowane wyniki. Pierwszy wiersz zawiera poprawny wydruk preorder tego drzewa, a drugi i trzeci odpowiednio poprawne wydruki inorder i postorder. Pierwsze drzewo to takie, którego wydruk preorder jest pierwszy alfabetycznie. Jeśli istnieje wiele takich drzew, wybierz spośród nich to, którego wydruk inorder jest pierwszy alfabetycznie.

Każde odtworzenie jest ciągiem 6 tokenów wybranych spośród Pre, In i Post. Odtworzenia porządkuje się leksykograficznie przy następującej kolejności tokenów: $\texttt{Pre} < \texttt{In} < \texttt{Post}$.

Przykład

Wejście 1

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Wyjście 1

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Wejście 2

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

Wyjście 2

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB