Anatoly Cheng McDougal багато в чому типовий студент. За будь-якої можливості він намагається копіювати та вставляти код, а не писати його з нуля. Такий підхід неминуче спричиняє проблеми. Наприклад, коли він уперше дізнався про прямий, симетричний і зворотний обходи дерев та отримав код виведення дерева в прямому порядку (показано нижче ліворуч), він просто скопіював його, перемістив оператор виведення на правильне місце й перейменував процедуру. Проте він забув перейменувати виклики процедур усередині коду, що призвело до показаного нижче помилкового коду симетричного та зворотного виведення.

void prePrint(TNode t)
{
  output(t.value);
  if (t.left != null)
    prePrint(t.left);
  if (t.right != null)
    prePrint(t.right);
}

void inPrint(TNode t)
{
  if (t.left != null)
    prePrint(t.left);
  output(t.value);
  if (t.right != null)
    prePrint(t.right);
}

void postPrint(TNode t)
{
  if (t.left != null)
    prePrint(t.left);
  if (t.right != null)
    prePrint(t.right);
  output(t.value);
}

У цей момент Anatoly повівся нетипово для студента: він справді протестував код! На жаль, коли результати виявилися неправильними, він повернувся до типової студентської поведінки. Він запанікував і почав випадково змінювати виклики в усіх трьох процедурах, сподіваючись усе виправити. Зайве казати, що ситуація стала ще гіршою, ніж спочатку.

Викладачка Anatoly протестувала код на випадковому дереві символів. Побачивши результати трьох процедур виведення, вона правильно здогадалася, що сталося. Однак замість того, щоб відразу подивитися код, вона вирішила спробувати відновити код Anatoly лише за результатами. Для цього вона зробила такі правильні припущення:

1. Оператор виведення в кожній процедурі розташований правильно (наприклад, між двома рекурсивними викликами в процедурі inPrint).

2. Серед шести рекурсивних викликів трьох процедур рівно два звертаються до prePrint, рівно два до inPrint і рівно два до postPrint, хоча вони можуть бути в неправильних процедурах.

Невдовзі викладачка зрозуміла, що відновити код Anatoly і тестове дерево за результатами непросто, а результат може бути неоднозначним. Ви маєте допомогти їй знайти всі можливі відновлення коду Anatoly. Крім того, для кожного відновлення слід знайти перше за абеткою дерево (як описано в розділі виведення), що дає спостережувані результати.

Вхідні дані

Вхідні дані містять один тестовий випадок. Він складається з трьох рядків символів на трьох окремих рядках: спостережуваних результатів процедур prePrint, inPrint і postPrint Anatoly (у такому порядку) на деякому тестовому дереві. Кожен рядок містить $n$ великих літер ($4 \le n \le 26$), причому всередині кожного рядка літери не повторюються. Гарантовано існування хоча б одного розв’язку.

Вихідні дані

Виведіть усі можливі відновлення для тестового випадку в порядку, описаному в останньому абзаці нижче. Виведення кожного відновлення складається з двох частин. Перша частина — один рядок, що описує шість викликів у процедурах Anatoly: спочатку два (рекурсивні) виклики в prePrint, далі виклики в inPrint і нарешті в postPrint. Виклики позначаються словами Pre, In і Post, розділеними пробілами. Наприклад, якби процедури Anatoly були правильними, перша частина відновлення мала б вигляд Pre Pre In In Post Post.

Друга частина складається з трьох рядків і описує перше тестове дерево, яке могло породити спостережувані результати. Перший рядок містить правильний прямий обхід дерева, другий і третій — правильні симетричний і зворотний обходи відповідно. Першим є дерево, чий прямий обхід іде першим за абеткою. Якщо таких дерев кілька, серед них обирається дерево, чий симетричний обхід іде першим за абеткою.

Кожне відновлення — послідовність із 6 токенів, вибраних із Pre, In і Post. Відновлення впорядковуються лексикографічно за таким порядком токенів: $\texttt{Pre} < \texttt{In} < \texttt{Post}$.

Приклади

Вхідні дані 1

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Вихідні дані 1

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Вхідні дані 2

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

Вихідні дані 2

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB