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