Вгору по дереву#5660
Анатолій — типовий студент у багатьох сенсах. Щоразу, коли це можливо, він намагається копіювати й вставляти код, замість того щоб писати його з нуля. Такий підхід неминуче створює йому проблеми. Наприклад, коли він уперше дізнався про прямий, симетричний і зворотний обхід дерева й отримав код для прямого обходу (preorder), він просто скопіював код, переніс оператор виведення у правильне місце й перейменував процедуру. Однак він забув перейменувати виклики процедур усередині коду, у результаті чого отримав некоректний код для симетричного (inorder) та зворотного (postorder) обходу.
У цей момент Анатолій поводився не як типовий студент — він справді протестував свій код! На жаль, коли з'ясувалося, що результат був неправильним, він знову став поводитися як типовий студент: запанікував і почав довільно змінювати виклики у всіх трьох процедурах, сподіваючись на правильний результат. Зрозуміло, це лише погіршило ситуацію.
Викладачка Анатолія тестувала код на випадковому дереві з символів. Коли вона подивилася на вивід трьох процедур, вона здогадалася, що сталося. Однак, замість того щоб одразу переглянути код, вирішила спробувати відтворити код лише за отриманим виводом. Для цього вона зробила такі припущення:
Оператор виведення у кожній процедурі розташований у правильному місці (наприклад, між двома рекурсивними викликами у inPrint).
Серед шести рекурсивних викликів, що здійснюються у трьох процедурах, рівно два — до prePrint, два — до inPrint і два — до postPrint; вони можуть бути у неправильних процедурах.
Невдовзі викладачка зрозуміла: відтворити код Анатолія та дерево лише за отриманим виводом — завдання непросте, і воно може бути неоднозначним. Ви маєте допомогти їй знайти всі можливі відтворення коду Анатолія. До того ж, для кожного такого варіанта потрібно знайти дерево з лексикографічно мінімальним прямим обходом (див. у розділі виводу).
Вхід складається з одного тесту. Тест містить три рядки: вивід процедур prePrint, inPrint, postPrint (саме в такому порядку) для деякого дерева. Кожен рядок містить великих літер (4 \leq n \leq 26), причому всі символи у кожному рядку різні. Гарантується, що існує хоча б одне рішення.
Виведіть усі можливі відтворення, впорядковані так, як зазначено нижче. Вивід для кожного варіанта складається з двох частин. Перша частина — один рядок, що описує шість викликів процедур Анатолія: перші два (рекурсивних) виклики з prePrint, далі з inPrint, далі з postPrint. Виклики описуються словами Pre, In, Post, розділеними пробілами. Якби всі процедури були коректними, перша частина виглядала б як Pre Pre In In Post Post.
Друга частина складається з трьох рядків — перший містить (правильний) прямий (preorder) обхід дерева, другий і третій — відповідно симетричний (inorder) та зворотний (postorder) обходи цього дерева. Якщо дерев-кандидатів з мінімальним прямим обходом декілька, виведіть те, у якого симетричний обхід найменший.
Кожне відтворення — це послідовність з токенів (Pre, In, Post); сортуйте їх лексикографічно з урахуванням порядку: Pre In Post.
Приклад 1