Anatoly Cheng McDougal adalah mahasiswa yang biasa dalam banyak hal. Kapan pun memungkinkan, ia mencoba menyalin dan menempelkan kode alih-alih menulisnya dari awal. Cara ini tak terhindarkan menimbulkan masalah. Contohnya, ketika pertama kali mempelajari penelusuran pohon preorder, inorder, dan postorder serta diberi kode untuk mencetak pohon secara preorder (ditunjukkan di kiri bawah), ia hanya menyalin dan menempelkan kode, memindahkan pernyataan cetak ke posisi yang benar, lalu mengganti nama prosedurnya. Namun, ia lupa mengganti nama pemanggilan prosedur di dalam kode, sehingga menghasilkan kode pencetakan inorder dan postorder yang salah seperti di bawah.

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);
}

Pada saat itu, Anatoly tidak bertindak seperti mahasiswa biasa: ia benar-benar menguji kodenya! Sayangnya, ketika hasilnya salah, ia kembali ke perilaku mahasiswa biasa. Ia panik dan mulai mengubah pemanggilan dalam ketiga prosedur secara acak, berharap bisa memperbaikinya. Tentu saja, situasinya justru menjadi lebih buruk daripada semula.

Dosen Anatoly menguji kode pada sebuah pohon karakter acak. Ketika melihat keluaran ketiga rutin pencetaknya, ia menebak dengan benar apa yang telah terjadi. Namun, alih-alih langsung melihat kode, ia memutuskan mencoba merekonstruksi kode Anatoly hanya dengan mengamati keluarannya. Untuk itu, ia membuat asumsi-asumsi benar berikut:

1. Pernyataan keluaran di setiap rutin pencetak berada pada posisi yang benar (misalnya, di antara dua pemanggilan rekursif pada rutin inPrint).

2. Dari enam pemanggilan rekursif dalam ketiga rutin, tepat dua memanggil prePrint, tepat dua memanggil inPrint, dan tepat dua memanggil postPrint, meskipun mungkin berada dalam rutin yang salah.

Dosen itu segera menyadari bahwa merekonstruksi kode Anatoly dan pohon uji dari keluarannya bukan tugas sederhana, dan hasilnya mungkin ambigu. Anda harus membantunya menemukan semua kemungkinan rekonstruksi kode Anatoly. Selain itu, untuk setiap rekonstruksi, Anda harus menemukan pohon pertama secara alfabetis (seperti dijelaskan dalam bagian keluaran) yang menghasilkan keluaran yang diamati.

Masukan

Masukan terdiri dari satu kasus uji. Kasus uji terdiri dari tiga string pada tiga baris terpisah: keluaran yang diamati dari rutin prePrint, inPrint, dan postPrint Anatoly (dalam urutan tersebut) pada suatu pohon uji. Setiap string terdiri dari $n$ huruf kapital ($4 \le n \le 26$), tanpa huruf berulang di dalam string mana pun. Dijamin ada setidaknya satu solusi.

Keluaran

Tampilkan semua kemungkinan rekonstruksi untuk kasus uji, diurutkan seperti dijelaskan pada paragraf terakhir di bawah. Keluaran setiap rekonstruksi terdiri dari dua bagian. Bagian pertama berupa satu baris yang menjelaskan enam pemanggilan dalam rutin Anatoly: pertama dua pemanggilan (rekursif) pada prePrint, lalu pemanggilan pada inPrint, dan terakhir pemanggilan pada postPrint. Pemanggilan dijelaskan dengan kata Pre, In, dan Post, dipisahkan oleh spasi. Misalnya, jika rutin Anatoly benar, bagian pertama rekonstruksi akan berupa Pre Pre In In Post Post.

Bagian kedua terdiri dari tiga baris dan menjelaskan pohon uji pertama yang mungkin menghasilkan keluaran yang diamati. Baris pertama adalah pencetakan preorder yang benar dari pohon, sedangkan baris kedua dan ketiga masing-masing berisi pencetakan inorder dan postorder yang benar. Pohon pertama adalah pohon dengan pencetakan preorder yang pertama secara alfabetis. Jika ada beberapa pohon seperti itu, pilih yang pencetakan inorder-nya pertama secara alfabetis di antara pohon-pohon tersebut.

Setiap rekonstruksi adalah urutan 6 token yang dipilih dari Pre, In, dan Post. Rekonstruksi diurutkan secara leksikografis menurut urutan token berikut: $\texttt{Pre} < \texttt{In} < \texttt{Post}$.

Contoh

Masukan 1

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Keluaran 1

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Masukan 2

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

Keluaran 2

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB