Вверх по дереву
Анатолий - типичный студент во многих смыслах. Всякий раз он пытается копипастить код вместо написания с нуля. Такой подход неизбежно доставляет ему проблемы. Например, когда он впервые познакомился с разными порядками обхода бинарных деревьев post, pre и in и получил код pre-обхода с вызовом функции вывода вершины output, он просто скопировал код, перенес вызов output в правильное место и переименовал функцию. Однако он забыл переименовать функции в теле обхода, получив неправильные функции обходов.
И тут Анатолий проявил себя не как типичный студент - он стал тестировать свой код! К сожалению, когда он увидел, что функции работают неправильно, он стал вести себя как обычный студент снова. Он стал паниковать и случайным образом переименовывать вызовы функций во всех трех обходах, надеясь, что они начнут работать правильно.
Преподаватель Анатолия тестировала его код на случайных деревьях с символами в вершинах. Когда она посмотрела на выходные данные программы, то поняла, что случилось. Тем не менее, вместо того, чтобы посмотреть код, она попробовала восстановить код по его выводу. Для этого она сделала справедливые предположения:
команда вывода символа находится на правильном месте, например, между вызовами функций в inPrint обходе;
среди всех 6 рекурсивных вызовов ровно по два вызова inPrint, prePrint и postPrint, возможно, стоящих в неправильных местах.
Вскоре преподаватель поняла, что восстановление кода Анатолия и тестового дерева по выводу программы не такая простая задача и что результат может быть неоднозначным. Вам предстоит помочь ей найти все возможные реконструкции кода Анатолия. Вдобавок, для каждого восстановленного кода необходимо найти лексикографически наименьшее дерево по выходным данным программы.
Входные данные
Входные данные состоят из одного теста, содержащего три строки - выходные строки функций соответственно prePrint, inPrint и postPrint. Строки имеют одинаковую длину n (4 ≤ n ≤ 26), все символы каждой из строк различны. Гарантируется, что хотя бы одно решение существует.
Выходные данные
Выведите все возможные восстановления, упорядоченные как приведено ниже. Для каждого восстановления следует вывести две части. Первая часть состоит из одной строки и содержит шесть вызовов процедур Анатолия: первые два (рекурсивных) вызова процедуры prePrint, за которыми следуют вызовы процедуры inPrint, и наконец вызовы postPrint. Указанные вызовы описываются словами Pre, In и Post, разделенными пробелами. Например, если бы процедуры Анатолия были корректны, то первая часть содержала бы строку Pre Pre In In Post Post..
Вторая часть состоит из трех строк и описывает первое тестовое дерево, которое может сгенерировать наблюдаемый вывод. Первая строка содержит корректный вывод дерева в порядке preorder, вторая и третья строки - корректный вывод дерева в порядке inorder и postorder соответственно. Первое дерево содержит алфавитно наименьший preorder вывод. Если и таких деревьев несколько, то выводить следует то, у которого inorder вывод алфавитно наименьший.
Каждое восстановление - это последовательность из 6 элементов, выбранных из Pre, In и Post. Порядок восстановлений определяется порядком на элементах: Pre < In < Post.