트리 복원

Anatoly는 여러모로 평범한 학생이다. 가능하면 코드를 처음부터 작성하기보다 복사해서 붙여넣으려 하는데, 그 습관이 늘 문제를 일으킨다. 트리의 전위(preorder), 중위(inorder), 후위(postorder) 순회를 처음 배웠을 때 그는 동작하는 전위 출력 루틴 코드를 받았다. 그는 그 코드를 두 번 복사한 뒤 각 복사본에서 출력문만 올바른 위치로 옮기고 이름을 바꿔 중위 루틴과 후위 루틴을 만들었다. 그런데 복사본 안의 재귀 호출 이름을 바꾸는 것을 잊어버려서 inPrint와 postPrint 루틴이 망가지고 말았다.

이번만큼은 Anatoly가 실제로 코드를 테스트했다. 결과가 틀리자 그는 당황했고, 평범한 학생답게 세 루틴의 재귀 호출을 마구잡이로 바꾸며 우연히라도 맞기를 바랐다. 상황은 더 나빠졌을 뿐이다.

Anatoly의 교수님은 무작위로 만든 문자 트리에 세 루틴을 실행했다. 출력만 보고 무슨 일이 있었는지 짐작한 교수님은 출력만으로 그의 코드와 테스트 트리를 복원하기로 했다. 교수님은 다음 두 가지 사실에 의존할 수 있었다.

1. 각 루틴에서 출력문은 올바른 위치에 있다. prePrint는 두 재귀 호출보다 먼저 자기 노드를 출력하고, inPrint는 두 호출 사이에서 출력하며, postPrint는 두 호출 뒤에 출력한다.
2. 세 루틴이 만드는 여섯 개의 재귀 호출 중에서 정확히 두 개는 prePrint를, 정확히 두 개는 inPrint를, 정확히 두 개는 postPrint를 호출한다. 다만 엉뚱한 루틴 안에 들어가 있을 수 있다.

복원 결과는 여러 가지일 수 있으므로, 가능한 모든 복원을 구해야 한다. 그리고 각 복원마다 관측된 출력을 만들어 낼 수 있는 사전순으로 가장 앞선 트리도 함께 구해야 한다.

입력은 하나의 테스트 케이스로, 서로 다른 세 줄에 세 개의 문자열이 주어진다. 각 줄은 어떤 테스트 트리에 대해 Anatoly의 prePrint, inPrint, postPrint 루틴이 이 순서대로 만들어 낸 관측 출력이다. 각 문자열은 서로 다른 대문자 $4 \le n \le 26$개로 이루어지며, 한 문자열 안에 같은 글자가 반복되지 않는다. 적어도 하나의 복원이 존재함이 보장된다.

가능한 모든 복원을, 마지막에 설명한 순서대로 출력한다. 각 복원은 두 부분으로 이루어진다.

첫 부분은 한 줄로, 여섯 개의 재귀 호출을 설명한다. 먼저 prePrint의 두 호출, 그다음 inPrint의 두 호출, 마지막으로 postPrint의 두 호출 순이다. 각 호출은 Pre, In, Post 중 하나로 적고 하나의 공백으로 구분한다. 예를 들어 Anatoly의 루틴이 올바랐다면 이 줄은 Pre Pre In In Post Post가 된다.

둘째 부분은 세 줄로, 관측된 출력을 만들어 낼 수 있는 사전순으로 가장 앞선 트리를 설명한다. 첫 줄은 그 트리의 올바른 전위 순회, 둘째 줄은 올바른 중위 순회, 셋째 줄은 올바른 후위 순회이다. '사전순으로 가장 앞선'이란 올바른 전위 순회가 사전순으로 가장 작은 트리를 뜻하며, 그런 트리가 여럿이면 올바른 중위 순회가 사전순으로 가장 작은 트리를 택한다.

각 복원은 Pre, In, Post에서 고른 여섯 개의 토큰 수열이다. 복원들은 토큰 순서 Pre < In < Post를 기준으로 사전순으로 정렬해 출력한다.