Anatoly Cheng McDougal é, em muitos aspetos, um estudante típico. Sempre que possível, tenta copiar e colar código em vez de o escrever de raiz. Inevitavelmente, esta abordagem causa-lhe problemas. Por exemplo, quando aprendeu os percursos de árvores em pré-ordem, em ordem e em pós-ordem e recebeu código para imprimir uma árvore em pré-ordem (mostrado abaixo à esquerda), limitou-se a copiar e colar o código, mover a instrução de impressão para a posição correta e mudar o nome do procedimento. Contudo, esqueceu-se de mudar os nomes das chamadas dentro do código, originando o código incorreto de impressão em ordem e em pós-ordem mostrado abaixo.

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

Nesse momento, Anatoly não se comportou como um estudante típico: chegou mesmo a testar o código! Infelizmente, quando os resultados não foram corretos, regressou ao comportamento típico de estudante. Entrou em pânico e começou a alterar aleatoriamente as chamadas nos três procedimentos, na esperança de acertar. Escusado será dizer que a situação ficou ainda pior do que ao início.

A professora de Anatoly testou o código numa árvore aleatória de caracteres. Ao observar a saída das suas três rotinas de impressão, adivinhou corretamente o que tinha acontecido. Porém, em vez de ir diretamente ao código, decidiu tentar reconstruí-lo apenas observando a saída. Para isso, fez as seguintes suposições corretas:

1. A instrução de saída de cada rotina de impressão está na posição correta (por exemplo, entre as duas chamadas recursivas da rotina inPrint).

2. Das seis chamadas recursivas nas três rotinas, exatamente duas são para prePrint, exatamente duas para inPrint e exatamente duas para postPrint, embora possam estar nas rotinas erradas.

A professora percebeu rapidamente que reconstruir o código de Anatoly e a árvore de teste a partir da saída não era simples e que o resultado podia ser ambíguo. Terás de a ajudar a encontrar todas as reconstruções possíveis do código de Anatoly. Além disso, para cada reconstrução, deves encontrar a primeira árvore por ordem alfabética (conforme descrito na secção da saída) que produza a saída observada.

Entrada

A entrada contém um único caso de teste. Este consiste em três cadeias em três linhas separadas: a saída observada das rotinas prePrint, inPrint e postPrint de Anatoly (por esta ordem) numa determinada árvore de teste. Cada cadeia contém $n$ letras maiúsculas ($4 \le n \le 26$), sem letras repetidas dentro de qualquer cadeia. É garantido que existe pelo menos uma solução.

Saída

Apresenta todas as reconstruções possíveis para o caso de teste, ordenadas como descrito no último parágrafo abaixo. A saída de cada reconstrução tem duas partes. A primeira é uma única linha que descreve as seis chamadas nas rotinas de Anatoly: primeiro as duas chamadas (recursivas) em prePrint, seguidas das chamadas em inPrint e, finalmente, das chamadas em postPrint. As chamadas são descritas pelas palavras Pre, In e Post, separadas por espaços. Por exemplo, se as rotinas de Anatoly estivessem corretas, a primeira parte da reconstrução seria Pre Pre In In Post Post.

A segunda parte consiste em três linhas e descreve a primeira árvore de teste que poderia ter gerado as saídas observadas. A primeira linha é a impressão correta em pré-ordem da árvore, e a segunda e terceira contêm as impressões corretas em ordem e em pós-ordem, respetivamente. A primeira árvore é a que tem a primeira impressão em pré-ordem por ordem alfabética. Se houver várias árvores assim, escolhe-se, entre elas, a que tem a primeira impressão em ordem por ordem alfabética.

Cada reconstrução é uma sequência de 6 símbolos escolhidos de Pre, In e Post. As reconstruções são ordenadas lexicograficamente com a seguinte ordem dos símbolos: $\texttt{Pre} < \texttt{In} < \texttt{Post}$.

Exemplos

Entrada 1

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Saída 1

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Entrada 2

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

Saída 2

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB