Up a Tree

Anatoly is a typical student in many ways. Whenever possible he copies and pastes code instead of writing it from scratch, and that habit keeps causing him trouble. When he first learned about the preorder, inorder and postorder traversals of a tree, he was handed working code for a preorder print routine. He copied it twice, moved the print statement to the right spot in each copy, and renamed the copies to make an inorder and a postorder routine. Unfortunately he forgot to rename the recursive procedure calls inside the copies, so his inPrint and postPrint routines came out broken.

For once Anatoly actually tested his code. When the results were wrong he panicked and, like a typical student, began randomly changing the recursive calls in all three routines, hoping to stumble onto something correct. This only made things worse.

Anatoly's professor ran the three routines on a random tree of letters. Looking only at the output, she guessed what had happened and decided to reconstruct both his code and the test tree from the output alone. She relied on two facts:

1. In each routine the print statement sits in its correct place: prePrint prints its node before both recursive calls, inPrint prints between the two calls, and postPrint prints after both calls.
2. Among the six recursive calls made by the three routines, exactly two call prePrint, exactly two call inPrint and exactly two call postPrint, although they may sit in the wrong routines.

The reconstruction can be ambiguous, so she wants every possible reconstruction, and for each one the alphabetically first tree that produces the observed output.

The input is a single test case: three strings on three separate lines, giving the observed output of Anatoly's prePrint, inPrint and postPrint routines (in that order) on some test tree. Each string is made of $4 \le n \le 26$ uppercase letters with no repeated letter. At least one reconstruction is guaranteed to exist.

List every possible reconstruction, ordered as described at the end. Each reconstruction has two parts.

The first part is a single line describing the six recursive calls: first the two calls in prePrint, then the two calls in inPrint, and finally the two calls in postPrint. Each call is written as Pre, In or Post, separated by single spaces. For example, if Anatoly's routines had been correct this line would read Pre Pre In In Post Post.

The second part is three lines describing the alphabetically first tree that could have produced the observed output: the tree's correct preorder print, then its correct inorder print, then its correct postorder print. Alphabetically first means the tree whose correct preorder print is alphabetically smallest; if several trees share that preorder print, take the one whose correct inorder print is alphabetically smallest.

Every reconstruction is a sequence of six tokens taken from Pre, In and Post. Order the reconstructions lexicographically using the token order Pre < In < Post.