Вверх по дереву
Анатолій - типовий студент у багатьох розуміннях. Кожного разу він пропує копіпастити код замість написання з нуля. Такий підхід постійно доставляє йому проблеми. Наприклад, коли він вперше познайомився з різними порядками обходу бінарних деревьев 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.