Anatoly Cheng McDougal es un estudiante típico en muchos aspectos. Siempre que puede, intenta copiar y pegar código en lugar de escribirlo desde cero. Inevitablemente, esto le causa problemas. Por ejemplo, cuando aprendió los recorridos en preorden, inorden y postorden de árboles y recibió código para imprimir un árbol en preorden (mostrado abajo a la izquierda), simplemente copió y pegó el código, movió la instrucción de impresión a la posición correcta y cambió el nombre del procedimiento. Sin embargo, olvidó cambiar los nombres de las llamadas dentro del código, lo que produjo el código defectuoso de impresión en inorden y postorden que se muestra abajo.

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

En ese momento, Anatoly no se comportó como un estudiante típico: ¡realmente probó su código! Por desgracia, cuando los resultados fueron incorrectos, volvió al comportamiento típico de estudiante. Entró en pánico y empezó a cambiar aleatoriamente las llamadas de los tres procedimientos, con la esperanza de arreglarlo. Como era de esperar, la situación empeoró aún más respecto al principio.

La profesora de Anatoly probó el código en un árbol aleatorio de caracteres. Al observar la salida de sus tres rutinas de impresión, adivinó correctamente lo sucedido. Sin embargo, en lugar de consultar directamente el código, decidió intentar reconstruirlo observando solo la salida. Para ello, hizo las siguientes suposiciones correctas:

1. La instrucción de salida de cada rutina está en la posición correcta (por ejemplo, entre las dos llamadas recursivas de la rutina inPrint).

2. De las seis llamadas recursivas de las tres rutinas, exactamente dos llaman a prePrint, exactamente dos a inPrint y exactamente dos a postPrint, aunque pueden estar en las rutinas equivocadas.

Pronto la profesora comprendió que reconstruir el código de Anatoly y el árbol de prueba a partir de la salida no era sencillo y que el resultado podía ser ambiguo. Debes ayudarla a encontrar todas las reconstrucciones posibles del código de Anatoly. Además, para cada reconstrucción debes encontrar el primer árbol en orden alfabético (según se describe en la sección de salida) que genere la salida observada.

Entrada

La entrada consta de un único caso de prueba: tres cadenas en tres líneas separadas, que contienen la salida observada de las rutinas prePrint, inPrint y postPrint de Anatoly (en ese orden) sobre algún árbol de prueba. Cada cadena contiene $n$ letras mayúsculas ($4 \le n \le 26$), sin letras repetidas dentro de ninguna cadena. Se garantiza que hay al menos una solución.

Salida

Muestra todas las reconstrucciones posibles del caso de prueba, ordenadas como se indica en el último párrafo de abajo. La salida de cada reconstrucción tiene dos partes. La primera es una sola línea que describe las seis llamadas de las rutinas de Anatoly: primero las dos llamadas (recursivas) de prePrint, después las de inPrint y, por último, las de postPrint. Las llamadas se describen con las palabras Pre, In y Post, separadas por espacios. Por ejemplo, si las rutinas de Anatoly fueran correctas, la primera parte de la reconstrucción sería Pre Pre In In Post Post.

La segunda parte consta de tres líneas y describe el primer árbol de prueba que podría haber generado las salidas observadas. La primera línea es la impresión correcta en preorden del árbol, y la segunda y tercera contienen sus impresiones correctas en inorden y postorden, respectivamente. El primer árbol es aquel cuya impresión en preorden es la primera alfabéticamente. Si hay varios árboles así, se elige entre ellos el que tenga la primera impresión en inorden alfabéticamente.

Cada reconstrucción es una secuencia de 6 símbolos elegidos entre Pre, In y Post. Las reconstrucciones se ordenan lexicográficamente según el siguiente orden de símbolos: $\texttt{Pre} < \texttt{In} < \texttt{Post}$.

Ejemplos

Entrada 1

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Salida 1

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Entrada 2

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

Salida 2

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB