Anatoly Cheng McDougal est, à bien des égards, un étudiant typique. Dès qu’il le peut, il essaie de copier-coller du code plutôt que de l’écrire de zéro. Cette approche lui cause inévitablement des problèmes. Par exemple, lorsqu’il a découvert les parcours préfixe, infixe et postfixe des arbres et reçu du code pour afficher un arbre en ordre préfixe (ci-dessous à gauche), il a simplement copié-collé le code, déplacé l’instruction d’affichage au bon endroit et renommé la procédure. Il a toutefois oublié de renommer les appels de procédures à l’intérieur du code, produisant les codes incorrects d’affichage infixe et postfixe ci-dessous.

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

À ce stade, Anatoly ne s’est pas comporté comme un étudiant typique : il a réellement testé son code ! Malheureusement, lorsque les résultats se sont révélés incorrects, il a repris un comportement typique d’étudiant. Pris de panique, il a commencé à modifier au hasard les appels dans les trois procédures, en espérant obtenir le bon résultat. Inutile de dire que la situation est devenue encore pire qu’au départ.

La professeure d’Anatoly a testé le code sur un arbre aléatoire de caractères. En regardant les sorties des trois routines d’affichage, elle a correctement deviné ce qui s’était passé. Cependant, au lieu de consulter directement le code, elle a décidé de tenter de le reconstituer en observant uniquement les sorties. Pour cela, elle a fait les hypothèses correctes suivantes :

1. L’instruction d’affichage de chaque routine est au bon endroit (par exemple, entre les deux appels récursifs dans la routine inPrint).

2. Parmi les six appels récursifs des trois routines, exactement deux appellent prePrint, exactement deux appellent inPrint et exactement deux appellent postPrint, même s’ils peuvent se trouver dans les mauvaises routines.

La professeure a vite compris que reconstituer le code d’Anatoly et l’arbre de test à partir des sorties n’était pas simple et que le résultat pouvait être ambigu. Vous devez l’aider à trouver toutes les reconstitutions possibles du code d’Anatoly. De plus, pour chacune, vous devez trouver le premier arbre par ordre alphabétique (comme décrit dans la section de sortie) donnant les sorties observées.

Entrée

L’entrée contient un seul cas de test, composé de trois chaînes sur trois lignes distinctes : les sorties observées des routines prePrint, inPrint et postPrint d’Anatoly (dans cet ordre) sur un certain arbre de test. Chaque chaîne contient $n$ lettres majuscules ($4 \le n \le 26$), sans lettre répétée à l’intérieur d’une chaîne. Il est garanti qu’au moins une solution existe.

Sortie

Affichez toutes les reconstitutions possibles pour le cas de test, dans l’ordre décrit au dernier paragraphe ci-dessous. La sortie de chaque reconstitution comporte deux parties. La première est une seule ligne décrivant les six appels des routines d’Anatoly : d’abord les deux appels (récursifs) de prePrint, puis ceux de inPrint, et enfin ceux de postPrint. Les appels sont décrits par les mots Pre, In et Post, séparés par des espaces. Par exemple, si les routines d’Anatoly étaient correctes, la première partie serait Pre Pre In In Post Post.

La seconde partie contient trois lignes et décrit le premier arbre de test qui pourrait avoir produit les sorties observées. La première ligne est l’affichage correct en ordre préfixe de l’arbre ; les deuxième et troisième lignes contiennent ses affichages corrects en ordres infixe et postfixe, respectivement. Le premier arbre est celui dont l’affichage préfixe est le premier par ordre alphabétique. S’il en existe plusieurs, choisissez parmi eux celui dont l’affichage infixe est le premier par ordre alphabétique.

Chaque reconstitution est une séquence de 6 symboles choisis parmi Pre, In et Post. Les reconstitutions sont triées lexicographiquement selon l’ordre de symboles suivant : $\texttt{Pre} < \texttt{In} < \texttt{Post}$.

Exemples

Entrée 1

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Sortie 1

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Entrée 2

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

Sortie 2

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB